Martin Farach-Colton Professor Rutgers University Dept. of Computer Science Center for Discrete Mathematics and Theoretical Computer Science Piscataway. NJ 08854 (732) 445-0074 FAX - 5932 farach@dimacs.rutgers.edu

Computational Biology. Protein-Protein Interaction Networks. string algorithms for nucleic acid comparisons and database retrievals

I am interested in computational Biology. with emphasis on the construction of evolutionary trees and on string algorithms for nucleic acid comparison and database retrieval. I am also working on design and analysis of sequential and parallel algorithms. particularly those dealing with with string matching.

Selected Publications

Farach-Colton. M. and Shah. R. On the Complexity of Ordinal Clustering. Journal of Classification accepted for publication.

Choi. V. and Farach-Colton. M. Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes. Gene 320 (2003) 165--176.

Bender. M. and Farach-Colton. M. (2004). The Level Ancestor Problem Simplified. Theoretical Computer Science Special Issue on LATIN '02. To appear.

Bender. M.. Demaine. E. and Farach-Colton. M. (2004). Cache-oblivious B-Trees. SIAM Journal on Computing. in press

Bartal. Y.. Farach-Colton. M.. Yooseph. S. and Zhang. L.(2002) Fast. fair and frugal bandwidth allocation in ATM networks." Algorithmic 33(3):272--286.

Cole. R. . Farach-Colton. M.. Hariharan. R.. Przytycka. T. and Throup. M. (2000) An $O(n\log n)$ algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal of Computing 30(5):1385--1404.

Farach-Colton. M. and Liberatore. V. (2000) On local register allocation. J. Alogrithms 37(1):37--65.

Chen. K.. Durand. D. and Farach-Colton. M. (2000) Notung: Dating gene duplications using gene family trees. Journal of Computational Biology 7(3-4):429--447.

Farach-Colton. M.. Ferragina,P. and Muthukrishnan. S. (2000) On the sorting-complexity of suffix tree construction. Journal of the Association for Computing Machinery 47(6):987--1011.

Farach. M. and Kannan. S. (1999) Efficient algorithms for inverting evolution. Journal of the Association for Computing Machinery 46(4):437--449.

Agarwala. R. . Bafna. V.. Farach. M.. Paterson. M. and Thorup. M. (1999) On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing 28(3):1073--1085.

Amir. A.. Benson. G. and Farach. M. (1998) Optimal parallel two dimensional text searching on a CREW PRAM. Information and Computation 144(1):1--17.

Farach. M. and Thorup. M. (1998) String matching in Lempel-Ziv compressed strings. Algorithmica 20(4):388--404.