Martin Farach-Colton

Bing Citeseer DBLP Google Google Scholar Kosmix Wikipedia Yahoo!
Loading Google Thumbnails...
2013
91Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound). Martin Farach-Colton, Antonio Fernández Anta, Miguel A. Mosteiro. Theor. Comput. Sci. (472): 60-80 (2013). Web SearchBibTeXDownload
2012
90Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism. Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks. LATIN 2012, 303-314. Web SearchBibTeXDownload
89Don't Thrash: How to Cache Your Hash on Flash. Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, Erez Zadok. PVLDB (5): 1627-1637 (2012). Web SearchBibTeXDownload
2011
88Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution. Paulo Sérgio Almeida, Carlos Baquero, Martin Farach-Colton, Paulo Jesus, Miguel A. Mosteiro. CoRR (abs/1109.4373) (2011). Web SearchBibTeXDownload
87Opportunistic Information. Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks. CoRR (abs/1105.6151) (2011). Web SearchBibTeXDownload
86Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: - Adaptiveness vs. Obliviousness and Randomization vs. Determinism. Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks. DISC 2011, 202-204. Web SearchBibTeXDownload
2009
85Bootstrapping a hop-optimal network in the weak sensor model. Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro. ACM Transactions on Algorithms (5) (2009). Web SearchBibTeXDownload
84Efficient and Robust Prediction Algorithms for Protein Complexes Using Gomory-Hu Trees. Antonina Mitrofanova, Martin Farach-Colton, Bud Mishra. Pacific Symposium on Biocomputing 2009, 215-226. Web SearchBibTeXDownload
2008
83Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics. Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos. ACM Transactions on Algorithms (4) (2008). Web SearchBibTeXDownload
82A Linear Delay Algorithm for Building Concept Lattices. Martin Farach-Colton, Yang Huang. CPM 2008, 204-216. Web SearchBibTeXDownload
81Fast and compact regular expression matching. Philip Bille, Martin Farach-Colton. Theor. Comput. Sci. (409): 486-496 (2008). Web SearchBibTeXDownload
2007
80Introduction to SODA 2002 and 2003 special issue. Harold N. Gabow, Michael A. Bender, Martin Farach-Colton. ACM Transactions on Algorithms (3) (2007). Web SearchBibTeXDownload
79Sensor Network Gossiping or How to Break the Broadcast Lower Bound. Martin Farach-Colton, Miguel A. Mosteiro. ISAAC 2007, 232-243. Web SearchBibTeXDownload
78Optimal spaced seeds for faster approximate string matching. Martin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur. J. Comput. Syst. Sci. (73): 1035-1044 (2007). Web SearchBibTeXDownload
77Lattice based Clustering of Temporal Gene-Expression Matrices. Yang Huang, Martin Farach-Colton. SDM 2007. Web SearchBibTeXDownload
76Cache-oblivious streaming B-trees. Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson. SPAA 2007, 81-92. Web SearchBibTeXDownload
75Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model. Martin Farach-Colton, Miguel A. Mosteiro. WADS 2007, 565-576. Web SearchBibTeXDownload
2006
74On the Complexity of Ordinal Clustering. Rahul Shah, Martin Farach-Colton. J. Classification (23): 79-102 (2006). Web SearchBibTeXDownload
73Lower Bounds for Clear Transmissions in Radio Networks. Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro. LATIN 2006, 447-454. Web SearchBibTeXDownload
72Cache-oblivious string B-trees. Michael A. Bender, Martin Farach-Colton, Bradley C. Kuszmaul. PODS 2006, 233-242. Web SearchBibTeXDownload
71Insertion Sort is O(n log n). Michael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro. Theory Comput. Syst. (39): 391-397 (2006). Web SearchBibTeXDownload
2005
70Fast and Compact Regular Expression Matching. Philip Bille, Martin Farach-Colton. CoRR (abs/cs/0509069) (2005). Web SearchBibTeXDownload
69Bootstrapping a Hop-Optimal Network in the Weak Sensor Model. Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro. ESA 2005, 827-838. Web SearchBibTeXDownload
68Optimal Spaced Seeds for Faster Approximate String Matching. Martin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur. ICALP 2005, 1251-1262. Web SearchBibTeXDownload
67Lowest common ancestors in trees and directed acyclic graphs. Michael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin. J. Algorithms (57): 75-94 (2005). Web SearchBibTeXDownload
66Cache-Oblivious B-Trees. Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. SIAM J. Comput. (35): 341-358 (2005). Web SearchBibTeXDownload
65Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos. SODA 2005, 650-659. Web SearchBibTeXDownload
64Adversarial contention resolution for simple channels. Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson. SPAA 2005, 325-332. Web SearchBibTeXDownload
2004
63Insertion Sort is O(n log n). Michael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro. CoRR (cs.DS/0407003) (2004). Web SearchBibTeXDownload
62Adversarial Analyses of Window Backoff Strategies. Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson. IPDPS Next Generation Software Program - NSFNGS - PI Workshop 2004. Web SearchBibTeXDownload
61Discovering temporal relations in molecular pathways using protein-protein interactions. Martin Farach-Colton, Yang Huang, John L. L. Woolford. RECOMB 2004, 150-156. Web SearchBibTeXDownload
60The Level Ancestor Problem simplified. Michael A. Bender, Martin Farach-Colton. Theor. Comput. Sci. (321): 5-12 (2004). Web SearchBibTeXDownload
59Finding frequent items in data streams. Moses Charikar, Kevin Chen, Martin Farach-Colton. Theor. Comput. Sci. (312): 3-15 (2004). Cited by 15Web SearchBibTeXDownload
2003
58Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes. Vicky Choi, Martin Farach-Colton. CoRR (cs.DS/0302005) (2003). Web SearchBibTeXDownload
57Adventures at Google. Martin Farach-Colton. ENC 2003, 3. Web SearchBibTeXDownload
2002
56Fast, Fair and Frugal Bandwidth Allocation in ATM Networks. Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang. Algorithmica (33): 272-286 (2002). Web SearchBibTeXDownload
55Efficient Tree Layout in a Multilevel Memory Hierarchy. Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, Mikkel Thorup. ESA (cs.DS/0211010): 165-173 (2002). Web SearchBibTeXDownload
54Two Simplified Algorithms for Maintaining Order in a List. Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito. ESA 2002, 152-164. Web SearchBibTeXDownload
53Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton. ESA 2002, 139-151. Web SearchBibTeXDownload
52Finding Frequent Items in Data Streams. Moses Charikar, Kevin Chen, Martin Farach-Colton. ICALP 2002, 693-703. Web SearchBibTeXDownload
51The Level Ancestor Problem Simplified. Michael A. Bender, Martin Farach-Colton. LATIN 2002, 508-515. Web SearchBibTeXDownload
50Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. Rahul Shah, Martin Farach-Colton. SODA 2002, 108-115. Web SearchBibTeXDownload
2001
49On the midpath tree conjuncture: a counter-example. Rahul Shah, Martin Farach-Colton. SODA 2001, 208-209. Web SearchBibTeXDownload
2000
48COFE: A Scalable Method for Feature Extraction from Complex Objects. Gabriela Hristescu, Martin Farach-Colton. DaWaK 2000, 358-371. Web SearchBibTeXDownload
47Cache-Oblivious B-Trees. Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. FOCS 2000, 399-409. Web SearchBibTeXDownload
46On the sorting-complexity of suffix tree construction. Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan. J. ACM (47): 987-1011 (2000). Cited by 96Web SearchBibTeXDownload
45On Local Register Allocation. Martin Farach-Colton, Vincenzo Liberatore. J. Algorithms (37): 37-65 (2000). Web SearchBibTeXDownload
44NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees. Kevin Chen, Dannie Durand, Martin Farach-Colton. Journal of Computational Biology (7): 429-447 (2000). Web SearchBibTeXDownload
43The LCA Problem Revisited. Michael A. Bender, Martin Farach-Colton. LATIN 2000, 88-94. Web SearchBibTeXDownload
42Notung: dating gene duplications using gene family trees. Kevin Chen, Dannie Durand, Martin Farach-Colton. RECOMB 2000, 96-106. Web SearchBibTeXDownload
41An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa M. Przytycka, Mikkel Thorup. SIAM J. Comput. (30): 1385-1404 (2000). Web SearchBibTeXDownload
1999
40Evaluation of Algorithms for Local Register Allocation. Vincenzo Liberatore, Martin Farach-Colton, Ulrich Kremer. CC 1999, 137-152. Web SearchBibTeXDownload
39Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. Martin Farach-Colton, Piotr Indyk. FOCS 1999, 171-180. Cited by 24Web SearchBibTeXDownload
38On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup, Mikkel Thorup. SIAM J. Comput. (28): 1073-1085 (1999). Web SearchBibTeXDownload
37Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang. SODA 1999, 92-101. Web SearchBibTeXDownload
1998
36String Matching in Lempel-Ziv Compressed Strings. Martin Farach, Mikkel Thorup. Algorithmica (20): 388-404 (1998). Web SearchBibTeXDownload
35Overcoming the Memory Bottleneck in Suffix Tree Construction. Martin Farach, Paolo Ferragina, S. Muthukrishnan. FOCS 1998, 174-185. Cited by 67Web SearchBibTeXDownload
34Optimal Parallel Two Dimensional Text Searching on a CREW PRAM. Amihood Amir, Gary Benson, Martin Farach. Inf. Comput. (144): 1-17 (1998). Web SearchBibTeXDownload
33On Local Register Allocation. Martin Farach-Colton, Vincenzo Liberatore. SODA 1998, 564-573. Web SearchBibTeXDownload
1997
32Optimal Parallel Randomized Renaming. Martin Farach, S. Muthukrishnan. Inf. Process. Lett. (61): 7-10 (1997). Cited by 2Web SearchBibTeXDownload
31Optimal Two-Dimensional Compressed Matching. Amihood Amir, Gary Benson, Martin Farach. J. Algorithms (24): 354-379 (1997). Web SearchBibTeXDownload
30Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. Richa Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan, Steven Skiena. RECOMB 1997, 1-2. Web SearchBibTeXDownload
29Sparse Dynamic Programming for Evolutionary-Tree Comparison. Martin Farach, Mikkel Thorup. SIAM J. Comput. (26): 210-230 (1997). Web SearchBibTeXDownload
28Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model. Richa Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Sridhar Hannenhalli, Martin Farach, S. Muthukrishnan, Steven Skiena. SODA (4): 275-296 (1997). Web SearchBibTeXDownload
1996
27Perfect Hashing for Strings: Formalization and Algorithms. Martin Farach, S. Muthukrishnan. CPM 1996, 130-140. Cited by 9Web SearchBibTeXDownload
26Optimal Logarithmic Time Randomized Suffix Tree Construction. Martin Farach, S. Muthukrishnan. ICALP 1996, 550-561. Cited by 34Web SearchBibTeXDownload
25Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files. Amihood Amir, Gary Benson, Martin Farach. J. Comput. Syst. Sci. (52): 299-307 (1996). Web SearchBibTeXDownload
24On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup, Mikkel Thorup. SODA 1996, 365-372. Web SearchBibTeXDownload
1995
23Computing the Agreement of Trees with Bounded Degrees. Martin Farach, Teresa M. Przytycka, Mikkel Thorup. ESA 1995, 381-393. Web SearchBibTeXDownload
22Fast Comparison of Evolutionary Trees. Martin Farach, Mikkel Thorup. Inf. Comput. (123): 29-37 (1995). Web SearchBibTeXDownload
21Improved Dynamic Dictionary Matching. Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, Alejandro A. Schäffer. Inf. Comput. (119): 258-282 (1995). Web SearchBibTeXDownload
20Efficient 2-Dimensional Approximate Matching of Half-Rectangular Figures. Amihood Amir, Martin Farach. Inf. Comput. (118): 1-11 (1995). Web SearchBibTeXDownload
19On the Agreement of Many Trees. Martin Farach, Teresa M. Przytycka, Mikkel Thorup. Inf. Process. Lett. (55): 297-301 (1995). Web SearchBibTeXDownload
18Optimal Parallel Dictionary Matching and Compression (Extended Abstract). Martin Farach, S. Muthukrishnan. SPAA 1995, 244-253. Cited by 20Web SearchBibTeXDownload
17String matching in Lempel-Ziv compressed strings. Martin Farach, Mikkel Thorup. STOC 1995, 703-712. Web SearchBibTeXDownload
1994
16Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract). Martin Farach, Mikkel Thorup. FOCS 1994, 770-779. Web SearchBibTeXDownload
15Optimal Two-Dimensional Compressed Matching. Amihood Amir, Gary Benson, Martin Farach. ICALP 1994, 215-226. Web SearchBibTeXDownload
14Alphabet Dependence in Parameterized Matching. Amihood Amir, Martin Farach, S. Muthukrishnan. Inf. Process. Lett. (49): 111-115 (1994). Cited by 54Web SearchBibTeXDownload
13Dynamic Dictionary Matching. Amihood Amir, Martin Farach, Zvi Galil, Raffaele Giancarlo, Kunsoo Park. J. Comput. Syst. Sci. (49): 208-222 (1994). Web SearchBibTeXDownload
12An Alphabet Independent Approach to Two-Dimensional Pattern Matching. Amihood Amir, Gary Benson, Martin Farach. SIAM J. Comput. (23): 313-323 (1994). Web SearchBibTeXDownload
11Let Sleeping Files Lie: Pattern Matching in Z-compressed Files. Amihood Amir, Gary Benson, Martin Farach. SODA 1994, 705-714. Web SearchBibTeXDownload
10Fast Comparison of Evolutionary Trees. Martin Farach, Mikkel Thorup. SODA 1994, 481-488. Web SearchBibTeXDownload
1993
9Improved Dynamic Dictionary Matching. Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, Alejandro A. Schäffer. SODA 1993, 392-401. Web SearchBibTeXDownload
8Optimal Parallel Two Dimensional Pattern Matching. Amihood Amir, Gary Benson, Martin Farach. SPAA 1993, 79-85. Web SearchBibTeXDownload
1992
7Efficient Randomized Dictionary Matching Algorithms (Extended Abstract). Amihood Amir, Martin Farach, Yossi Matias. CPM 1992, 262-275. Cited by 35Web SearchBibTeXDownload
6Two-Dimensional Dictionary Matching. Amihood Amir, Martin Farach. Inf. Process. Lett. (44): 233-239 (1992). Web SearchBibTeXDownload
5Alphabet Independent Two Dimensional Matching. Amihood Amir, Gary Benson, Martin Farach. STOC 1992, 59-68. Web SearchBibTeXDownload
1991
4Efficient matching of nonrectangular shapes. Amihood Amir, Martin Farach. Ann. Math. Artif. Intell. (4): 211-224 (1991). Web SearchBibTeXDownload
3Adaptive Dictionary Matching. Amihood Amir, Martin Farach. FOCS 1991, 760-766. Web SearchBibTeXDownload
2Optimal Superprimitivity Testing for Strings. Alberto Apostolico, Martin Farach, Costas S. Iliopoulos. Inf. Process. Lett. (39): 17-20 (1991). Web SearchBibTeXDownload
1Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures. Amihood Amir, Martin Farach. SODA 1991, 212-223. Web SearchBibTeXDownload
from DBLP and Google Scholar
References
1. ^ Computer Science Colloquium - NYU Computer Science Department - Retrieved 2011-04-23 - details
2. ^ DCS Faculty - Retrieved 2011-06-12 - details
3. ^ Past Distinguished Lecture Series - Retrieved 2013-05-12 - details
4. ^ Untitled Document - Retrieved 2013-05-13 - details
Developed by the Database Group at the University of Wisconsin and Yahoo! Research