Martin Farach-Colton is an American

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

, known for his work in

streaming algorithm In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically one-pass algorithm, just one. These algorithms are desi ...

suffix tree In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particu ...

construction,

pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...

in compressed data,

cache-oblivious algorithm In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An ...

s, and

lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a Tree (graph theory), tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and a ...

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s. He is the Leonard J. Shustek Professor of Computer Science and chair of the Department of Computer Science and Engineering at

New York University New York University (NYU) is a private university, private research university in New York City, New York, United States. Chartered in 1831 by the New York State Legislature, NYU was founded in 1832 by Albert Gallatin as a Nondenominational ...

. Formerly, he was a Distinguished Professor of Computer Science at

Rutgers University Rutgers University ( ), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of three campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's C ...

. He co-founded the storage technology startup company Tokutek..

Early life and education

Farach-Colton is of

Argentine Argentines, Argentinians or Argentineans are people from Argentina. This connection may be residential, legal, historical, or cultural. For most Argentines, several (or all) of these connections exist and are collectively the source of their ...

descent and grew up in

South Carolina South Carolina ( ) is a U.S. state, state in the Southeastern United States, Southeastern region of the United States. It borders North Carolina to the north and northeast, the Atlantic Ocean to the southeast, and Georgia (U.S. state), Georg ...

. While attending

medical school A medical school is a tertiary educational institution, professional school, or forms a part of such an institution, that teaches medicine, and awards a professional degree for physicians. Such medical degrees include the Bachelor of Medicine, ...

, he met his future husband, with whom he now has twin children. He obtained his M.D. in 1988 from the

Johns Hopkins School of Medicine The Johns Hopkins University School of Medicine (JHUSOM) is the medical school of Johns Hopkins University, a private research university in Baltimore, Maryland. Established in 1893 following the construction of the Johns Hopkins Hospital, th ...

and his Ph.D. in computer science in 1991 from the

University of Maryland, College Park The University of Maryland, College Park (University of Maryland, UMD, or simply Maryland) is a public university, public Land-grant university, land-grant research university in College Park, Maryland, United States. Founded in 1856, UMD i ...

under the supervision of Amihood Amir.

Research contributions

After completing his Ph.D., he went on to work at

Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...

and co-founded Tokutek. He was program chair of the 14th ACM-SIAM

Symposium on Discrete Algorithms The Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) is an academic conference in the fields of algorithm design and discrete mathematics. It is considered to be one of the top conferences for research in algorithms. SODA has been organized a ...

(SODA 2003). The cache-oblivious

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing fo ...

data structures studied by Bender, Demaine, and Farach-Colton beginning in 2000 became the basis for the

fractal tree index In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. L ...

used by Tokutek's products

TokuDB TokuDB is an open-source, high-performance storage engine for MySQL and MariaDB. It achieves this by using a fractal tree index. It is scalable, ACID and MVCC compliant, provides indexing-based query improvements, offers online schema modifi ...

and TokuMX.

Awards and honors

In 1996, Farach-Colton was awarded an

Alfred P. Sloan Research Fellowship The Sloan Research Fellowships are awarded annually by the Alfred P. Sloan Foundation since 1955 to "provide support and recognition to early-career scientists and scholars". This program is one of the oldest of its kind in the United States. ...

. In 2021, he was inducted as a

SIAM Fellow The SIAM Fellowship is an award and fellowship that recognizes outstanding members of the Society for Industrial and Applied Mathematics (SIAM). The goal of the program is to: *honor SIAM members who are recognized by their peers as distinguishe ...

"for contributions to the design and analysis of algorithms and their use in storage systems and

computational biology Computational biology refers to the use of techniques in computer science, data analysis, mathematical modeling and Computer simulation, computational simulations to understand biological systems and relationships. An intersection of computer sci ...

" and as an

ACM Fellow ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...

"for contributions to data structures for biocomputing and big data" In 2022, he was inducted as an

IEEE Fellow , the Institute of Electrical and Electronics Engineers The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and ot ...

"for contributions to data structures for storage systems". In 2023, he was elected to the Argentine Academia Nacional de Ciencias Exactas, Fisicas y Naturales. In 2024, he was inducted as an

AAAS Fellow Fellowship of the American Association for the Advancement of Science (FAAAS) is an honor accorded by the American Association for the Advancement of Science (AAAS) to distinguished persons who are members of the Association. Fellows are elected ...

. In 2012, his paper "The LCA problem revisited" won the Simon Imre Test of Time award at LATIN. In 2016, his paper "Optimizing Every Operation in a Write-optimized File System" won the Best Paper award at FAST. In 2023, his paper "Mosaic Pages: Big TLB Reach with Small Pages" won a Distinguished Paper award as ASPLOS.

Personal life

Farach-Colton is an avid Brazilian jiu-jitsu practitioner and received a bronze medal at the 2015 World Master Jiu-Jitsu IBJJF Championship. He received his black belt from Russell Kerr in 2018. Farach-Colton has served on several charity boards including the

Ali Forney Center The Ali Forney Center (AFC), based in New York City, is the largest LGBT community center helping LGBTQ homeless youth in the United States. The AFC both manages and develops transitional housing for its clients. AFC helps approximately 2,000 ...

Lambda Legal The Lambda Legal Defense and Education Fund, better known as Lambda Legal, is an American civil rights organization that focuses on lesbian, gay, bisexual, and transgender (LGBTQ) communities as well as people living with HIV/AIDS ( PWAs) throug ...

, and

The Trevor Project The Trevor Project is an American nonprofit organization founded in 1998. Focused on suicide prevention efforts for lesbian, gay, bisexual, transgender, queer, and questioning (LGBTQ) youth, they offer a toll-free telephone number where con ...

. He is the 2025 recipient of the

Luminary Award.Ali Forney Center Instagram
/ref>

Selected publications

*. *. *. *. *. Previously announced in ICALP 2002. *. Previously announced at FOCS 2000.

References

External links

Home pageGoogle scholar profile
{{DEFAULTSORT:Farach-Colton, Martin Year of birth missing (living people) Living people American people of Argentine descent American LGBTQ scientists American theoretical computer scientists University of Maryland, College Park alumni Rutgers University faculty LGBTQ people from South Carolina LGBTQ Hispanic and Latino American people American LGBTQ academics Argentine computer scientists Fellows of the Society for Industrial and Applied Mathematics Fellows of the IEEE 2021 fellows of the Association for Computing Machinery Fellows of the American Association for the Advancement of Science American practitioners of Brazilian jiu-jitsu People awarded a black belt in Brazilian jiu-jitsu 21st-century American LGBTQ people