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 ...
s,
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
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 ...
Luminary Award.
Ali Forney Center Instagram
/ref>
Selected publications
*.
*.
*.
*.
*. Previously announced in ICALP 2002.
*. Previously announced at FOCS 2000.
References
External links
Home page
Google 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