Refereed Journal Publications

  1. M. Farach-Colton and R. Shah. "On the Complexity of Ordinal Clustering." Journal of Classification accepted for publication.
  2. V. Choi and M. Farach-Colton. "Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes." Gene 320 (2003) 165--176.
  3. M. Bender and M. Farach-Colton. "The Level Ancestor Problem Simplified." Theoretical Computer Science Special Issue on LATIN '02, 2004. To appear
  4. M. Bender, E. Demaine and M. Farach-Colton. "Cache-Oblivious B-Trees." SIAM Journal on Computing, in press 2004.
  5. Y. Bartal, M. Farach-Colton, S. Yooseph, and L. Zhang. "Fast, Fair and Frugal Bandwidth Allocation in ATM Networks." Algorithmica, 33(3):272--286 (2002)
  6. R. Cole, M. Farach-Colton, R. Hariharan, T. Przytycka and M. Throup, "An $O(n\log n)$ Algorithm for the Maximum Agreement Subtree Problem for Binary Trees." SIAM Journal of Computing, 30(5):1385--1404 (2000)
  7. M. Farach-Colton and V. Liberatore. "On Local Register Allocation." J. Alogrithms 37(1):37--65 (2000)
  8. K. Chen, D. Durand, and M. Farach-Colton. "Notung: Dating gene duplications using gene family trees." Journal of Computational Biology, 7(3-4):429--447 (2000)
  9. M. Farach-Colton, P. Ferragina and S. Muthukrishnan. "On the Sorting-Complexity of Suffix Tree Construction." Journal of the Association for Computing Machinery, 47(6):987--1011 (2000)
  10. M. Farach and S. Kannan. "Efficient Algorithms for Inverting Evolution." Journal of the Association for Computing Machinery, 46(4):437--449 (1999)
  11. R. Agarwala, V. Bafna, M. Farach, M. Paterson and M. Thorup. "On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)." SIAM Journal on Computing, 28(3):1073--1085 (1999)
  12. A. Amir, G. Benson and M. Farach. "Optimal Parallel Two Dimensional Text Searching on a CREW PRAM." Information and Computation, 144(1):1--17 (1998)
  13. M. Farach and M. Thorup. "String Matching in Lempel-Ziv Compressed Strings." Algorithmica 20(4):388--404 (1998)
  14. M. Farach and S. Muthukrishnan. "Optimal Parallel Randomized Renaming." Information Processing Letters, Vol 61, pp. 7--10, 1997
  15. M. Farach and M. Thorup. " Sparse Dynamic Programming for Evolutionary Tree Comparison." SIAM Journal on Computing, Vol 26, No 1, pp. 210--230, 1997
  16. A. Amir, G. Benson and M. Farach. "Optimal Two Dimensional Compressed Matching." Journal of Algorithms, Vol 24, pp. 354--379, 1997
  17. M. Farach. "Recognizing Circular Decomposable Metrics." Journal of Computational Biology, Vol 4, pp. 157--162, 1997
  18. Richa Agarwala, Serafim Batzoglou, Vlado Dan\v c\'\i. Scott Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan and Steven Skiena, "Local Rules for Protein Folding on the Triangular Lattice and Generalized Hydrophobicity in the HP Model." Journal of Computational Biology, 4(3):275--296 (1997)
  19. Jaime Cohen and Martin Farach. "Numerical Taxonomy on Data: Experimental Results." Journal of Computational Biology,1997, pp 547-558
  20. A. Amir, G. Benson and M. Farach. "Let Sleeping Files Lie: Pattern Matching in Z-compressed Files." Journal of Computer and System Science, Vol 52, No 2, pp. 299--307, 1996
  21. M. Farach, T. Przytycka and M. Thorup. "On the Agreement of Many Trees." Information Processing Letters, Vol 55, pp. 297--301, 1995
  22. M. Farach and M. Thorup. "Fast Comparison of Evolutionary Trees." Information and Computation, Vol 123, No. 1, pp.29--37, 1995
  23. A. Amir, M. Farach, R. Idury, H. La Poutr\'e and A. Sch\"affer, "Improved Dynamic Dictionary Matching." Information and Computation, Vol 119, No. 2, pp. 258--282, 1995
  24. A. Amir, M. Farach and S. Muthukrishnan. "Alphabet Dependence in Parameterized Matching." Information Processing Letters, Vol 49, No. 3, pp. 111-120, 1995
  25. A. Amir and M. Farach. "Efficient 2-dimensional Approximate Matching of Half-rectangular Figures." Information and Computation, Vol 118, No. 1, pp. 1-11, 1995
  26. M. Farach, S. Kannan and T. Warnow. "A Robust Model for Finding Optimal Evolutionary Trees." Algorithmica, Special Issue on Computational Biology, Vol 13, pp. 155-179, 1995
  27. A. Amir, M. Farach, R. Giancarlo, Z. Galil and K. Park. "Dynamic Dictionary Matching." Journal of Computer and Systems Science, Vol 49, No. 2, pp. 208-222, 1994
  28. A. Amir, G. Benson and M. Farach. "An Alphabet Independent Approach to Two Dimensional Pattern Matching." SIAM Journal on Computing, Vol 23, No. 2, pp. 313-323, 1994
  29. A. Amir and M. Farach. "Two Dimensional Dictionary Matching." Information Processing Letters, Vol 44, pp. 233-239, 1992
  30. A. Apostolico, M. Farach and C. Iliopoulos. "Optimal Superprimitivity Testing for Strings." Information Processing Letters, Vol 39, pp. 17--20, 1991
  31. A. Amir and M. Farach. "Efficient Matching of Nonrectangular Shapes." Annals of Mathematics and Artificial Intelligence, Vol 4, 1991
  32. J. Wald, M. Farach, M. Tagamets and J. Reggia. "Generating Plausible Diagnostic Hypotheses with Self-processing Causal Networks." Journal of Experimental and Theoretical Artificial Intelligence, Vol 1. #2, 1989

Refereed Conference Publications

  1. M. Farach-Colton, Y. Huang and J. Woolford. "Discovering Temporal Relations in Molecular Pathways Using Protein-Protein Interactions." RECOMB '04
  2. M. Bender and M. Farach-Colton. "The Level Ancestor Problem Simplified." LATIN, pages 508-515, 2002.
  3. M. Bender, R. Cole, E. Demaine, M. Farach-Colton and J. Zito, "Two Simplified Algorithms for Maintaining Order in a List." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 152-164, 2002.
  4. M. Bender, R. Cole, E. Demaine and M. Farach-Colton. "Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 139-151, 2002.
  5. M. Bender, E. Demaine and M. Farach-Colton. "Efficient Tree Layout in a Multilevel Memory Hierarchy." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 165-173, 2002. Full Version.
  6. M. Charikar, K. Chen and M. Farach-Colton. "Finding Frequent Items in Data Streams." International Colloquium on Automata,Languages, and Programming (ICALP '02) 508--515
  7. R. Shah and M. Farach-Colton. "Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees." Symposium on Discrete Algorithms (SODA '02) 108--115
  8. M. Farach-Colton and G. Hristescu. "Structure-based Feature Extraction from Protein Databases." 2001 International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences METMBS '01
  9. M. Farach-Colton and R. Shah. "On the Midpath Tree Conjecture: A Counter-Example." Symposium on Discrete Algorithms (SODA '01) 208--209
  10. M. Farach-Colton and G. Hristescu. "COFE: A Scalable Method for Feature Extraction from Complex Objects." 2nd International Conference on Data Warehousing and Knowledge Discovery DaWaK '00 358--371
  11. M. Bender and M. Farach-Colton. " The LCA Problem Revisited." LATIN '00 88--94
  12. K. Chen, D. Durand, and M. Farach-Colton. "Notung: Dating gene duplications using gene family trees." RECOMB '00 96--106.
  13. M. Bender, E. Demaine and M. Farach-Colton. "Cache-Oblivious B-Trees." Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 399-409, 2000.
  14. M. Farach-Colton and P. Indyk. "Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings." Foundations of Computer Science (FOCS '99) 171--180
  15. M. Farach-Colton, U. Kremer and V. Liberatore. "Evaluation of Algorithms for Local Register Allocation." International Conference on Compiler Construction (CC '99) 137--152
  16. Y. Bartal, M. Farach-Colton, S. Yooseph, and L. Zhang. "Fast, Fair and Frugal Bandwidth Allocation in ATM Networks." Symposium on Discrete Algorithms (SODA '99) 92--101.
  17. M. Farach, P. Ferragina and S. Muthukrishnan. "Overcoming Memory Bottlenecks in Suffix Tree Construction." Foundations of Computer Science (FOCS '98) 174--185.
  18. M. Farach-Colton and V. Liberatore. "On Local Register Allocation." Symposium on Discrete Algorithms (SODA '98) 564--573.
  19. A. Ambainis, R. Desper, M. Farach and S. Kannan. "Nearly Tight Bounds on the Learnability of Evolution." Foundations of Computer Science (FOCS '97) 524--533
  20. C. Womack and M. Farach. "Randomization, Rigor and Persuasiveness in Proofs." Logic and Mathematical Reasoning, Mexico City, Mexico, October 1997
  21. G. Hristescu, C. Benham, and M. Farach. "DNA Strand Separation Prediction: A Parallel Implementation." International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '97)
  22. M. Farach, S. Kannan, E. Knill and S. Muthukrishnan. "Group Testing Problems with Sequences in Experimental Molecular Biology." SEQUENCES '97, Possitano, Italy, June 1997
  23. M. Farach. "Optimal Suffix Tree Construction with Large Alphabets." Foundations of Computer Science (FOCS '97) 137--143.
  24. Jaime Cohen and Martin Farach. "Numerical Taxonomy on Data: Experimental Results." Symposium on Discrete Algorithms (SODA '97).
  25. Richa Agarwala, Serafim Batzoglou, Vlado Dan\v c\'\i. Scott Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan and Steven Skiena, "Local Rules for Protein Folding on the Triangular Lattice and Generalized Hydrophobicity in the HP Model." Symposium on Discrete Algorithms (SODA '97) 390--399.
  26. M. Farach and S. Muthukrishnan. "Perfect Hashing for Strings: Formalization, Algorithms and Open Problems." Symposium on Combinatorial Pattern Matching (CPM '96), Laguna Beach, California, July 1996
  27. G. Christopher, M. Farach and M. Trick. "The Structure of Circular Decomposable Metrics." European Symposium on Algorithms (ESA '96).
  28. R. Agarwala, V. Bafna, M. Farach, M. Paterson and M. Thorup. "On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)." Symposium on Discrete Algorithms (SODA '96), 365--372.
  29. M. Farach and S. Kannan. "Efficient Algorithms for Inverting Evolution." Symposium on the Theory of Computing (STOC '96).
  30. M. Farach and S. Muthukrishnan. "Optimal Logarithmic Time Randomized Suffix Tree Construction." International Colloquium on Automata Languages and Programming (ICALP '96).
  31. M. Farach, T. Przytycka and M. Thorup. "Computing the Agreement of Trees with Bounded Degrees." European Symposium on Algorithms (ESA '95) 381--393.
  32. M. Farach and S. Muthukrishnan. "Optimal Parallel Dictionary Matching and Compression." Symposium on Parallel Algorithms and Architectures (SPAA '95) pp. 244-253, Santa Barbara, California, July 1995
  33. M. Farach, M. Noordewier, S. Savari, L. Shepp, A. Weiner and J. Ziv, "On the Entropy of DNA: Algorithms and Measurements based on Memory and Rapid Convergence." Symposium on Discrete Algorithms (SODA '95) pp. 48--57, San Fransisco, January 1995
  34. M. Farach and M. Thorup. "String Matching in Lempel-Ziv Compressed Strings." Symposium on the Theory of Computing (STOC '95), 703--712.
  35. M. Gu., M. Farach and R. Beigel. "An Efficient Algorithm for Dynamic Text Indexing." Symposium on Discrete Algorithms (SODA '94) pp. 697--704, Washington, DC, January 1994
  36. M. Farach and M. Thorup. " Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming." Foundations of Computer Science (FOCS '94) 770--779.
  37. A. Amir, G. Benson and M. Farach. "Let Sleeping Files Lie: Pattern Matching in Z-compressed Files." Symposium on Discrete Algorithms (SODA '94) 705--714.
  38. M. Farach and M. Thorup. "Fast Comparison of Evolutionary Trees." Symposium on Discrete Algorithms (SODA '94) 481--488.
  39. A. Amir, G. Benson and M. Farach. "Optimal Two Dimensional Compressed Matching." International Colloquium on Automata Languages and Programming (ICALP '94).
  40. M. Farach, S. Kannan and T. Warnow. "A Robust Model for Finding Optimal Evolutionary Trees." Symposium on the Theory of Computing (STOC '93) 137--145.
  41. A. Amir, G. Benson and M. Farach. "Parallel Two Dimensional Pattern Matching." Symposium on Parallel Algorithms and Architectures (SPAA '93), 79--85.
  42. A. Amir, M. Farach, R. Idury, H. La Poutr\'e and A. Sch\"affer, "Improved Dynamic Dictionary Matching." Symposium on Discrete Algorithms (SODA '93) 392--401.
  43. A. Amir, M. Farach and Y. Matias. "Efficient Randomized Dictionary Matching Algorithms." Symposium on Combinatorial Pattern Matching (CPM '92), Tucson, Arizona, April 1992
  44. A. Amir, G. Benson and M. Farach. "Alphabet Independent Two Dimensional Matching." Symposium on the Theory of Computing (STOC '92) 59--68.
  45. A. Amir and M. Farach. "Adaptive Dictionary Matching." Foundations of Computer Science (FOCS '91) 760--761.
  46. A. Amir and M. Farach. "Efficient 2-dimensional Approximate Matching of Non-rectangular Figures." Symposium on Discrete Algorithms (SODA '91) 212--223.
  47. A. Amir and M. Farach. "The Whole is Faster than its Parts." Conference on the Foundations of Artificial Intelligence (FAI '89).