Martin Farach-Colton
{{Short description|American computer scientist}}
{{Infobox scientist
| name = Martin Farach-Colton
| image = Martin Farach-Colton 2013 Big Data Workshop.jpg
| caption = Farach-Colton at the 2013 White House Office of Science and Technology Policy Big Data Workshop
| birth_place =
| fields = Computer science
| workplaces = New York University
| alma_mater = Johns Hopkins School of Medicine, MD (1988)
University of Maryland, College Park, PhD (1991)
| thesis_title = String Algorithms for Template Matching
| thesis_year = 1991
| doctoral_advisor = Amihood Amir
}}
Martin Farach-Colton is an American computer scientist, known for his work in streaming algorithms, suffix tree construction, pattern matching in compressed data, cache-oblivious algorithms, and lowest common ancestor data structures. He is the Leonard J. Shustek Professor of Computer Science and chair of the Department of Computer Science and Engineering at New York University.[https://engineering.nyu.edu/news/meet-martin-farach-colton-new-chair-department-computer-science-and-engineering News], Tandon School of Engineering, NYU, retrieved 2024-04-24. Formerly, he was a Distinguished Professor of Computer Science at Rutgers University.[https://www.cs.rutgers.edu/people/professors Professors], Computer Science, Rutgers, retrieved 2022-07-17. [https://web.archive.org/web/20220817045619/https://www.cs.rutgers.edu/people/professors Archived] on 2022-08-17. He co-founded the storage technology startup company Tokutek.{{citation|title=Scaling MySQL and MariaDB to TBs: Interview with Martín Farach-Colton|first=Roberto V.|last=Zicari|date=October 8, 2012|url=http://www.odbms.org/blog/2012/10/scaling-mysql-and-mariadb-to-tbs-interview-with-martin-farach-colton/|work=ODBMS Industry Watch}}.
Early life and education
Farach-Colton is of Argentine descent and grew up in South Carolina. While attending medical school, he met his future husband, with whom he now has twin children.{{citation|last=Farach-Colton|first=Martin|title=Turing Centennial Post 5: Martin Farach-Colton|date=July 10, 2012|url=https://lucatrevisan.wordpress.com/2012/07/10/turing-centennial-post-5-martin-farach-colton/|work=in theory|editor-last=Trevisan|editor-first=Luca|editor-link=Luca Trevisan}}. He obtained his M.D. in 1988 from the Johns Hopkins School of Medicine[https://www.usenix.org/conference/fast17/speaker-or-organizer/martin-farach-colton-rutgers-university Usenix FAST] and his Ph.D. in computer science in 1991 from the University of Maryland, College Park under the supervision of Amihood Amir.{{mathgenealogy|id=70210}}
Research contributions
After completing his Ph.D., he went on to work at Google and co-founded Tokutek.{{Cite web|title=Alumni Hall Of Fame {{!}} UMD Department of Computer Science|url=https://www.cs.umd.edu/community/alumni/halloffame/14752|access-date=2021-10-08|website=www.cs.umd.edu}} He was program chair of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).[http://www.siam.org/meetings/da03/ 14th ACM-SIAM Symposium on Discrete Algorithms], SIAM, retrieved 2015-07-08. The cache-oblivious B-tree data structures studied by Bender, Demaine, and Farach-Colton beginning in 2000 became the basis for the fractal tree index used by Tokutek's products TokuDB and TokuMX.
Awards and honors
In 1996, Farach-Colton was awarded an Alfred P. Sloan Research Fellowship.{{Cite web |url=http://www.sloan.org/sloan-research-fellowships/past-fellows/ |title=Sloan Foundation, Past Fellows |access-date=2021-03-31 |archive-date=2016-11-06 |archive-url=https://web.archive.org/web/20161106043224/http://www.sloan.org/sloan-research-fellowships/past-fellows/ |url-status=dead }} In 2021, he was inducted as a SIAM Fellow "for contributions to the design and analysis of algorithms and their use in storage systems and computational biology"{{citation|url=https://sinews.siam.org/Details-Page/siam-announces-class-of-2021-fellows|title=SIAM Announces Class of 2021 Fellows|date=March 31, 2021|access-date=2021-04-03}} and as an ACM Fellow "for contributions to data structures for biocomputing and big data"[https://www.acm.org/media-center/2022/january/fellows-2021 ACM Names 71 Fellows for Computing Advances that are Driving Innovation] In 2022, he was inducted as an IEEE Fellow "for contributions to data structures for storage systems".{{citation|url=https://www.ieee.org/content/dam/ieee-org/ieee/web/org/about/fellows/2022-ieee-fellows-class.pdf|archive-url=https://web.archive.org/web/20211124083848/https://www.ieee.org/content/dam/ieee-org/ieee/web/org/about/fellows/2022-ieee-fellows-class.pdf|url-status=dead|archive-date=November 24, 2021|title=2022 NEWLY ELEVATED FELLOWS|date=November 22, 2022|access-date=2021-11-24}}
In 2023, he was elected to the Argentine Academia Nacional de Ciencias Exactas, Fisicas y Naturales.{{citation|url=https://www.youtube.com/watch?v=SMcdE9_eUrw|title=Incorporación del Dr. Martin Farach Colton|date=October 18, 2023|access-date=2023-11-28}} In 2024, he was inducted as an AAAS Fellow.{{citation|url=https://www.aaas.org/page/2023-fellows|title=2023 AAAS FELLOWS|date=April 18, 2024|access-date=2024-04-19}}
In 2012, his paper "The LCA problem revisited" won the Simon Imre Test of Time award at LATIN.{{Cite web|title=LATIN|url=https://latintcs.org/imreprize.html|access-date=2021-10-08|website=latintcs.org}} In 2016, his paper "Optimizing Every Operation in a Write-optimized File System" won the Best Paper award at FAST.{{Cite web|title=Best Papers|url=https://www.usenix.org/conferences/best-papers?taxonomy_vocabulary_1_tid=2016&title_1=fast|access-date=2021-11-24|website=usenix.org}}
In 2023, his paper "Mosaic Pages: Big TLB Reach with Small Pages" won a Distinguished Paper award as ASPLOS.{{Cite web|title=ASPLOS 2023|url=https://asplos-conference.org/asplos2023/index.html|access-date=2023-11-28|website=asplos-conference.org}}
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.[http://static.ibjjfdb.com/Campeonato/000450/en-US/Results.pdf World Master Jiu-Jitsu IBJJF Championship 2015] He received his black belt from Russell Kerr in 2018.[https://www.instagram.com/p/BrYq4WEA-Pt/ Clockwork Jiu Jitsu Instagram] Farach-Colton has served on several charity boards including the Ali Forney Center, Lambda Legal,{{Cite web|title=Martin Farach-Colton|url=https://www.aliforneycenter.org/about-us/board-members1/martin-farach-colton/|access-date=2017-11-07|website=www.aliforneycenter.org|language=en}} and The Trevor Project.{{Cite web|title=Farach-Colton|url=https://www.thetrevorproject.org/board_member/farach-colton/|access-date=2020-09-04|website=www.thetrevorproject.org|language=en}} He is the 2025 recipient of the Ali Forney Center Luminary Award.[https://www.instagram.com/aliforneycenter/p/DHWI94Cxdri/ Ali Forney Center Instagram]
Selected publications
- {{citation
| last1 = Amir
| first1 = Amihood
| last2 = Benson
| first2 = Gary
| last3 = Farach
| first3 = Martin
| doi = 10.1006/jcss.1996.0023
| issue = 2
| journal = Journal of Computer and System Sciences
| mr = 1393996
| pages = 299–307
| title = Let sleeping files lie: pattern matching in Z-compressed files
| volume = 52
| date = April 1996
| citeseerx = 10.1.1.45.6476
| s2cid = 14465635
| url = http://tandem.bu.edu/papers/let.sleeping.files.lie.jcss.1996.pdf
| access-date = 2017-09-08
| archive-date = 2017-08-10
| archive-url = https://web.archive.org/web/20170810185228/http://tandem.bu.edu/papers/let.sleeping.files.lie.jcss.1996.pdf
| url-status = dead
}}.
- {{citation
| last = Farach | first = Martin
| contribution = Optimal suffix tree construction with large alphabets
| doi = 10.1109/SFCS.1997.646102
| pages = 137–143
| publisher = IEEE Computer Society
| title = 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997
| year = 1997
| isbn = 0-8186-8197-7
| citeseerx = 10.1.1.45.4336
| s2cid = 123355749
}}.
- {{citation
| last1 = Farach | first1 = M.
| last2 = Thorup | first2 = M. | author2-link = Mikkel Thorup
| doi = 10.1007/PL00009202
| issue = 4
| journal = Algorithmica
| mr = 1600834
| pages = 388–404
| title = String matching in Lempel-Ziv compressed strings
| volume = 20
| date = April 1998
| citeseerx = 10.1.1.45.5484
| s2cid = 15395909
}}.
- {{citation
| last1 = Bender | first1 = Michael A.
| last2 = Farach-Colton | first2 = Martin
| editor1-last = Gonnet | editor1-first = Gaston H.
| editor2-last = Panario | editor2-first = Daniel
| editor3-last = Viola | editor3-first = Alfredo
| contribution = The LCA problem revisited
| doi = 10.1007/10719839_9
| pages = 88–94
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings
| volume = 1776
| year = 2000
| isbn = 978-3-540-67306-4
| contribution-url = http://www.ics.uci.edu/%7Eeppstein/261/BenFar-LCA-00.pdf}}.
- {{citation
| last1 = Charikar | first1 = Moses | author1-link = Moses Charikar
| last2 = Chen | first2 = Kevin
| last3 = Farach-Colton | first3 = Martin
| doi = 10.1016/S0304-3975(03)00400-6
| issue = 1
| journal = Theoretical Computer Science
| mr = 2045483
| pages = 3–15
| title = Finding frequent items in data streams
| volume = 312
| year = 2004
| citeseerx = 10.1.1.145.8413
| url = https://www.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf}}. Previously announced in ICALP 2002.
- {{citation
| last1 = Bender | first1 = Michael A.
| last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine
| last3 = Farach-Colton | first3 = Martin
| doi = 10.1137/S0097539701389956
| issue = 2
| journal = SIAM Journal on Computing
| mr = 2191447
| pages = 341–358
| title = Cache-oblivious B-trees
| url = http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/
| volume = 35
| year = 2005
| citeseerx = 10.1.1.32.4093}}. Previously announced at FOCS 2000.
References
{{reflist}}
External links
- [http://www.cs.rutgers.edu/~farach/ Home page]
- [https://scholar.google.com/citations?user=2uHUSa8AAAAJ Google scholar profile]
{{authority control}}
{{DEFAULTSORT:Farach-Colton, Martin}}
Category:Year of birth missing (living people)
Category:American people of Argentine descent
Category:American LGBTQ scientists
Category:American theoretical computer scientists
Category:University of Maryland, College Park alumni
Category:Rutgers University faculty
Category:LGBTQ people from South Carolina
Category:LGBTQ Hispanic and Latino American people
Category:American LGBTQ academics
Category:Argentine computer scientists
Category:Fellows of the Society for Industrial and Applied Mathematics
Category:2021 fellows of the Association for Computing Machinery
Category:Fellows of the American Association for the Advancement of Science
Category:American practitioners of Brazilian jiu-jitsu