dblp.uni-trier.dewww.uni-trier.de

Martin Farach-Colton

Martin Farach

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2008
101EEMartin Farach-Colton, Yang Huang: A Linear Delay Algorithm for Building Concept Lattices. CPM 2008: 204-216
100EENoga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos: Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics. ACM Transactions on Algorithms 4(4): (2008)
99EEPhilip Bille, Martin Farach-Colton: Fast and compact regular expression matching. Theor. Comput. Sci. 409(3): 486-496 (2008)
2007
98EEMartin Farach-Colton, Miguel A. Mosteiro: Sensor Network Gossiping or How to Break the Broadcast Lower Bound. ISAAC 2007: 232-243
97EEYang Huang, Martin Farach-Colton: Lattice based Clustering of Temporal Gene-Expression Matrices. SDM 2007
96EEMichael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson: Cache-oblivious streaming B-trees. SPAA 2007: 81-92
95EEMartin Farach-Colton, Miguel A. Mosteiro: Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model. WADS 2007: 565-576
94EEHarold N. Gabow, Michael A. Bender, Martin Farach-Colton: Introduction to SODA 2002 and 2003 special issue. ACM Transactions on Algorithms 3(4): (2007)
93EEMartin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur: Optimal spaced seeds for faster approximate string matching. J. Comput. Syst. Sci. 73(7): 1035-1044 (2007)
92EEMary Cryan, Martin Farach-Colton: Preface. Theor. Comput. Sci. 382(2): 85 (2007)
2006
91EEMartin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro: Lower Bounds for Clear Transmissions in Radio Networks. LATIN 2006: 447-454
90EEMichael A. Bender, Martin Farach-Colton, Bradley C. Kuszmaul: Cache-oblivious string B-trees. PODS 2006: 233-242
89EEMichael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro: Insertion Sort is O(n log n). Theory Comput. Syst. 39(3): 391-397 (2006)
2005
88EEMartin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro: Bootstrapping a Hop-Optimal Network in the Weak Sensor Model. ESA 2005: 827-838
87EEMartin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur: Optimal Spaced Seeds for Faster Approximate String Matching. ICALP 2005: 1251-1262
86EENoga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos: Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. SODA 2005: 650-659
85EEMichael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson: Adversarial contention resolution for simple channels. SPAA 2005: 325-332
84EEPhilip Bille, Martin Farach-Colton: Fast and Compact Regular Expression Matching CoRR abs/cs/0509069: (2005)
83EEMichael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2): 75-94 (2005)
82EEMichael A. Bender, Erik D. Demaine, Martin Farach-Colton: Cache-Oblivious B-Trees. SIAM J. Comput. 35(2): 341-358 (2005)
2004
81 Martin Farach-Colton: LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings Springer 2004
80EEMichael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson: Adversarial Analyses of Window Backoff Strategies. IPDPS Next Generation Software Program - NSFNGS - PI Workshop 2004
79EEMartin Farach-Colton, Yang Huang, John L. L. Woolford: Discovering temporal relations in molecular pathways using protein-protein interactions. RECOMB 2004: 150-156
78EEMichael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro: Insertion Sort is O(n log n) CoRR cs.DS/0407003: (2004)
77EEMoses Charikar, Kevin Chen, Martin Farach-Colton: Finding frequent items in data streams. Theor. Comput. Sci. 312(1): 3-15 (2004)
76EEMichael A. Bender, Martin Farach-Colton: The Level Ancestor Problem simplified. Theor. Comput. Sci. 321(1): 5-12 (2004)
2003
75EEMartin Farach-Colton: Adventures at Google. ENC 2003: 3
74EEVicky Choi, Martin Farach-Colton: Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes CoRR cs.DS/0302005: (2003)
2002
73EEMichael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton: Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. ESA 2002: 139-151
72EEMichael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito: Two Simplified Algorithms for Maintaining Order in a List. ESA 2002: 152-164
71EEMichael A. Bender, Erik D. Demaine, Martin Farach-Colton: Efficient Tree Layout in a Multilevel Memory Hierarchy. ESA 2002: 165-173
70EEMoses Charikar, Kevin Chen, Martin Farach-Colton: Finding Frequent Items in Data Streams. ICALP 2002: 693-703
69EEMichael A. Bender, Martin Farach-Colton: The Level Ancestor Problem Simplified. LATIN 2002: 508-515
68EERahul Shah, Martin Farach-Colton: Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. SODA 2002: 108-115
67EEYair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang: Fast, Fair and Frugal Bandwidth Allocation in ATM Networks. Algorithmica 33(3): 272-286 (2002)
66EEStephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, Mikkel Thorup: Efficient Tree Layout in a Multilevel Memory Hierarchy CoRR cs.DS/0211010: (2002)
2001
65EERahul Shah, Martin Farach-Colton: On the midpath tree conjuncture: a counter-example. SODA 2001: 208-209
2000
64EEGabriela Hristescu, Martin Farach-Colton: COFE: A Scalable Method for Feature Extraction from Complex Objects. DaWaK 2000: 358-371
63 Michael A. Bender, Erik D. Demaine, Martin Farach-Colton: Cache-Oblivious B-Trees. FOCS 2000: 399-409
62 Michael A. Bender, Martin Farach-Colton: The LCA Problem Revisited. LATIN 2000: 88-94
61EEKevin Chen, Dannie Durand, Martin Farach-Colton: Notung: dating gene duplications using gene family trees. RECOMB 2000: 96-106
60EEMartin Farach-Colton, Paolo Ferragina, S. Muthukrishnan: On the sorting-complexity of suffix tree construction. J. ACM 47(6): 987-1011 (2000)
59 Martin Farach-Colton, Vincenzo Liberatore: On Local Register Allocation. J. Algorithms 37(1): 37-65 (2000)
58 Kevin Chen, Dannie Durand, Martin Farach-Colton: NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees. Journal of Computational Biology 7(3-4): 429-447 (2000)
57EERichard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa M. Przytycka, Mikkel Thorup: An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. SIAM J. Comput. 30(5): 1385-1404 (2000)
1999
56 Vincenzo Liberatore, Martin Farach-Colton, Ulrich Kremer: Evaluation of Algorithms for Local Register Allocation. CC 1999: 137-152
55EEMartin Farach-Colton, Piotr Indyk: Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. FOCS 1999: 171-180
54EEYair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang: Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. SODA 1999: 92-101
53EEMartin Farach, Sampath Kannan: Efficient Algorithms for Inverting Evolution. J. ACM 46(4): 437-449 (1999)
52 Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup: On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). SIAM J. Comput. 28(3): 1073-1085 (1999)
1998
51 Martin Farach-Colton: Combinatorial Pattern Matching, 9th Annual Symposium, CPM 98, Piscataway, New Jersey, USA, July 20-22, 1998, Proceedings Springer 1998
50EEMartin Farach, Paolo Ferragina, S. Muthukrishnan: Overcoming the Memory Bottleneck in Suffix Tree Construction. FOCS 1998: 174-185
49 Martin Farach, Vincenzo Liberatore: On Local Register Allocation. SODA 1998: 564-573
48 Martin Farach, Mikkel Thorup: String Matching in Lempel-Ziv Compressed Strings. Algorithmica 20(4): 388-404 (1998)
47 Amihood Amir, Gary Benson, Martin Farach: Optimal Parallel Two Dimensional Text Searching on a CREW PRAM. Inf. Comput. 144(1): 1-17 (1998)
1997
46EEMartin Farach: Optimal Suffix Tree Construction with Large Alphabets. FOCS 1997: 137-143
45EEAndris Ambainis, Richard Desper, Martin Farach, Sampath Kannan: Nearly Tight Bounds on the Learnability of Evolution. FOCS 1997: 524-533
44 Gabriela Hristescu, Craig J. Benham, Martin Farach: DNA Strand Separation Prediction: A Parallel Implementation. PDPTA 1997: 610-619
43EERicha Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan, Steven Skiena: Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. RECOMB 1997: 1-2
42EEJaime Cohen, Martin Farach: Numerical taxonomy on data (abstract): experimental results. RECOMB 1997: 98
41 Richa Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, Steven Skiena: Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model. SODA 1997: 390-399
40 Jaime Cohen, Martin Farach: Numerical Taxonomy on Data: Experimental Results. SODA 1997: 410-417
39EEMartin Farach, S. Muthukrishnan: Optimal Parallel Randomized Renaming. Inf. Process. Lett. 61(1): 7-10 (1997)
38 Amihood Amir, Gary Benson, Martin Farach: Optimal Two-Dimensional Compressed Matching. J. Algorithms 24(2): 354-379 (1997)
37 Martin Farach: Recognizing Circular Decompossible Metrics. Journal of Computational Biology 4(2): 157-162 (1997)
36 Richa Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Sridhar Hannenhalli, Martin Farach, S. Muthukrishnan, Steven Skiena: Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model. Journal of Computational Biology 4(3): 275-296 (1997)
35 Jaime Cohen, Martin Farach: Numerical Taxonomy on Data: Experimental Results. Journal of Computational Biology 4(4): 547-558 (1997)
34 Martin Farach, Mikkel Thorup: Sparse Dynamic Programming for Evolutionary-Tree Comparison. SIAM J. Comput. 26(1): 210-230 (1997)
1996
33 Martin Farach, S. Muthukrishnan: Perfect Hashing for Strings: Formalization and Algorithms. CPM 1996: 130-140
32 George Christopher, Martin Farach, Michael A. Trick: The Structure of Circular Decomposable Metrics. ESA 1996: 486-500
31 Martin Farach, S. Muthukrishnan: Optimal Logarithmic Time Randomized Suffix Tree Construction. ICALP 1996: 550-561
30 Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup: On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). SODA 1996: 365-372
29EEMartin Farach, Sampath Kannan: Efficient Algorithms for Inverting Evolution. STOC 1996: 230-236
28 Amihood Amir, Gary Benson, Martin Farach: Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files. J. Comput. Syst. Sci. 52(2): 299-307 (1996)
1995
27 Martin Farach, Teresa M. Przytycka, Mikkel Thorup: Computing the Agreement of Trees with Bounded Degrees. ESA 1995: 381-393
26 Martin Farach, Michiel O. Noordewier, Serap A. Savari, Larry A. Shepp, Aaron D. Wyner, Jacob Ziv: On the Entropy of DNA: Algorithms and Measurements Based on Memory and Rapid Convergence. SODA 1995: 48-57
25EEMartin Farach, S. Muthukrishnan: Optimal Parallel Dictionary Matching and Compression (Extended Abstract). SPAA 1995: 244-253
24EEMartin Farach, Mikkel Thorup: String matching in Lempel-Ziv compressed strings. STOC 1995: 703-712
23 Martin Farach, Sampath Kannan, Tandy Warnow: A Robust Model for Finding Optimal Evolutionary Trees. Algorithmica 13(1/2): 155-179 (1995)
22 Amihood Amir, Martin Farach: Efficient 2-Dimensional Approximate Matching of Half-Rectangular Figures Inf. Comput. 118(1): 1-11 (1995)
21 Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, Alejandro A. Schäffer: Improved Dynamic Dictionary Matching Inf. Comput. 119(2): 258-282 (1995)
20 Martin Farach, Mikkel Thorup: Fast Comparison of Evolutionary Trees. Inf. Comput. 123(1): 29-37 (1995)
19EEMartin Farach, Teresa M. Przytycka, Mikkel Thorup: On the Agreement of Many Trees. Inf. Process. Lett. 55(6): 297-301 (1995)
1994
18 Martin Farach, Mikkel Thorup: Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract) FOCS 1994: 770-779
17 Amihood Amir, Gary Benson, Martin Farach: Optimal Two-Dimensional Compressed Matching. ICALP 1994: 215-226
16 Martin Farach, Mikkel Thorup: Fast Comparison of Evolutionary Trees. SODA 1994: 481-488
15 Ming Gu, Martin Farach, Richard Beigel: An Efficient Algorithm for Dynamic Text Indexing. SODA 1994: 697-704
14 Amihood Amir, Gary Benson, Martin Farach: Let Sleeping Files Lie: Pattern Matching in Z-compressed Files. SODA 1994: 705-714
13 Amihood Amir, Martin Farach, S. Muthukrishnan: Alphabet Dependence in Parameterized Matching. Inf. Process. Lett. 49(3): 111-115 (1994)
12 Amihood Amir, Martin Farach, Zvi Galil, Raffaele Giancarlo, Kunsoo Park: Dynamic Dictionary Matching. J. Comput. Syst. Sci. 49(2): 208-222 (1994)
11 Amihood Amir, Gary Benson, Martin Farach: An Alphabet Independent Approach to Two-Dimensional Pattern Matching. SIAM J. Comput. 23(2): 313-323 (1994)
1993
10 Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, Alejandro A. Schäffer: Improved Dynamic Dictionary Matching. SODA 1993: 392-401
9EEAmihood Amir, Gary Benson, Martin Farach: Optimal Parallel Two Dimensional Pattern Matching. SPAA 1993: 79-85
8EEMartin Farach, Sampath Kannan, Tandy Warnow: A robust model for finding optimal evolutionary trees. STOC 1993: 137-145
1992
7 Amihood Amir, Martin Farach, Yossi Matias: Efficient Randomized Dictionary Matching Algorithms (Extended Abstract). CPM 1992: 262-275
6 Amihood Amir, Gary Benson, Martin Farach: Alphabet Independent Two Dimensional Matching STOC 1992: 59-68
5 Amihood Amir, Martin Farach: Two-Dimensional Dictionary Matching. Inf. Process. Lett. 44(5): 233-239 (1992)
1991
4 Amihood Amir, Martin Farach: Adaptive Dictionary Matching FOCS 1991: 760-766
3 Amihood Amir, Martin Farach: Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures. SODA 1991: 212-223
2 Amihood Amir, Martin Farach: Efficient matching of nonrectangular shapes. Ann. Math. Artif. Intell. 4: 211-224 (1991)
1 Alberto Apostolico, Martin Farach, Costas S. Iliopoulos: Optimal Superprimitivity Testing for Strings. Inf. Process. Lett. 39(1): 17-20 (1991)

Coauthor Index

1Richa Agarwala [30] [36] [41] [43] [52]
2Noga Alon [86] [100]
3Stephen Alstrup [66]
4Andris Ambainis [45]
5Amihood Amir [2] [3] [4] [5] [6] [7] [9] [10] [11] [12] [13] [14] [17] [21] [22] [28] [38] [47]
6Alberto Apostolico [1]
7Mihai Badoiu [86] [100]
8Vineet Bafna [30] [52]
9Yair Bartal [54] [67]
10Serafim Batzoglou [36] [41] [43]
11Richard Beigel [15]
12Michael A. Bender [62] [63] [66] [69] [71] [72] [73] [76] [78] [80] [82] [83] [85] [89] [90] [94] [96]
13Craig J. Benham [44]
14Gary Benson [6] [9] [11] [14] [17] [28] [38] [47]
15Philip Bille [84] [99]
16Moses Charikar [70] [77]
17Kevin Chen [58] [61] [70] [77]
18Vicky Choi [74]
19George Christopher [32]
20Jaime Cohen [35] [40] [42]
21Richard Cole [57] [72] [73]
22Mary Cryan [92]
23Vlado Dancík [36] [41] [43]
24Scott E. Decatur [36] [41] [43]
25Erik D. Demaine [63] [66] [71] [72] [73] [82] [86] [100]
26Richard Desper [45]
27Dannie Durand [58] [61]
28Rohan J. Fernandes [88] [91]
29Paolo Ferragina [50] [60]
30Jeremy T. Fineman [96]
31Yonatan R. Fogel [96]
32Harold N. Gabow [94]
33Zvi Galil [12]
34Raffaele Giancarlo [12]
35Ming Gu [15]
36Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi) [86] [100]
37Sridhar Hannenhalli [36] [41] [43]
38Ramesh Hariharan [57]
39Simai He [80] [85]
40Gabriela Hristescu [44] [64]
41Yang Huang [79] [97] [101]
42Ramana M. Idury [10] [21]
43Costas S. Iliopoulos [1]
44Piotr Indyk [55]
45Sampath Kannan [8] [23] [29] [45] [53]
46Ulrich Kremer [56]
47Bradley C. Kuszmaul [80] [85] [90] [96]
48Gad M. Landau [87] [93]
49Charles E. Leiserson [80] [85]
50Vincenzo Liberatore [49] [56] [59]
51Yossi Matias [7]
52Miguel A. Mosteiro [78] [88] [89] [91] [95] [98]
53J. Ian Munro [66]
54S. Muthukrishnan (S. Muthu Muthukrishnan) [13] [25] [31] [33] [36] [39] [43] [50] [60]
55Babu O. Narayanan [30]
56Jelani Nelson [96]
57Michiel O. Noordewier [26]
58Kunsoo Park [12]
59Mike Paterson [30] [52]
60Giridhar Pemmasani [83]
61Johannes A. La Poutré (Han La Poutré) [10] [21]
62Teresa M. Przytycka [19] [27] [57]
63Theis Rauhe [66]
64Süleyman Cenk Sahinalp [87] [93]
65Serap A. Savari [26]
66Alejandro A. Schäffer [10] [21]
67Rahul Shah [65] [68]
68Larry A. Shepp (Laurence A. Shepp) [26]
69Anastasios Sidiropoulos [86] [100]
70Steven Skiena [36] [41] [43] [83]
71Pavel Sumazin [83]
72Mikkel Thorup [16] [18] [19] [20] [24] [27] [30] [34] [48] [52] [57] [66]
73Michael A. Trick [32]
74Dekel Tsur [87] [93]
75Tandy Warnow [8] [23]
76John L. L. Woolford [79]
77Aaron D. Wyner [26]
78Shibu Yooseph [54] [67]
79Lisa Zhang [54] [67]
80Jack Zito [72]
81Jacob Ziv [26]

Colors in the list of coauthors

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)