Martin Farach-Colton

About

Martín Farach-Colton is the Leonard J. Shustek Professor of Computer Science and the Chair of the Department of Computer Science and Engineering at NYU Tandon School of Engineering. His research interests include the theory and practice of data structures for storage systems, graph algorithms, and streaming algorithms. He has contributed to applying mathematical principles to the development of algorithms and data structures, with a focus on storage and graph-related problems. Dr. Farach-Colton holds a B.S. in Mathematics and Chemistry from the University of South Carolina, an M.D. from The Johns Hopkins School of Medicine, and a Ph.D. in Computer Science from the University of Maryland. His work has been recognized through various honors, and he is actively involved in research through the Algorithms and Foundations Group at NYU Tandon.

Research topics

• Computer Science
• Algorithm
• Mathematics
• Theoretical computer science
• Operating system
• Parallel computing
• Combinatorics
• Discrete mathematics
• Business
• Programming language

Selected publications

• Tiny Pointers

  Society for Industrial and Applied Mathematics eBooks · 2023 · 10 citations

  This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n-bit pointers can be replaced with o(log n)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e.,…

  PublisherDOI

• Beyond Bloom: A Tutorial on Future Feature-Rich Filters

  2024-05-23 · 8 citations

  articleOpen access

  Filters, such as Bloom, quotient, and cuckoo, save space by maintaining an approximate representation of a set and occasionally returning false positives. Filters play a critical role in building modern dataintensive applications and are used across various domains such as databases, storage engines, computational biology, cyber- security, and networks. There has been extensive research on filters in the past few decades resulting in filters with much improved performance and features. Yet moder…

  PublisherDOI

• Adaptive Quotient Filters

  Proceedings of the ACM on Management of Data · 2024-09-30 · 5 citations

  articleOpen access

  Filters trade off accuracy for space and occasionally return false positive matches with a bounded error. Numerous systems use filters in fast memory to avoid performing expensive I/Os to slow storage. A fundamental limitation in traditional filters is that they do not change their representation upon seeing a false positive match. Therefore, the maximum false positive rate is only guaranteed for a single query, not for an arbitrary set of queries. We can improve the filter's performance on a st…

  PublisherDOI

• Mosaic Pages: Big TLB Reach With Small Pages

  IEEE Micro · 2024-06-06 · 4 citations

  article

  This article introduces mosaic pages, which increase translation lookaside buffer (TLB) reach by compressing multiple, discrete translations into one TLB entry. Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping. Mosaic reduces TLB misses in several workloads by 6%–81%…

  PublisherDOI

• History-Independent Concurrent Objects

  2024-06-05 · 2 citations

  article

  A data structure is called history independent if its internal memory representation does not reveal the history of operations applied to it, only its current state. In this paper we study history independence for concurrent data structures, and establish foundational possibility and impossibility results. We show that a large class of concurrent objects cannot be implemented from smaller base objects in a manner that is both wait-free and history independent; but if we settle for either lock-fr…

  PublisherDOI

Recent grants

• AitF: Collaborative Reserach: Theory and Implementation of Dynamic Data Structures for the GPU

  NSF · $365k · 2016–2020

• Collaborative Research: PPoSS: Planning: Efficient Address Translation with Formal Guarantees for Data-Center-Scale Applications

  NSF · $125k · 2021–2023

• BIGDATA: Mid-Scale: DCM: Collaborative Research: Eliminating the Data Ingestion Bottleneck in Big-Data Applications

  NSF · $406k · 2013–2017

Frequent coauthors

• Shubhangi Saraf

  Rutgers, The State University of New Jersey

  137 shared

• Michael A. Bender

  Stony Brook University

  125 shared

• Yuval Rabani

  122 shared

• Sandy Irani

  122 shared

• Michael Dinitz

  121 shared

• Avrim Blum

  121 shared

• Ronitt Rubinfeld

  Massachusetts Institute of Technology

  121 shared

• Robert Kleinberg

  121 shared

Awards & honors

• Leonard J. Shustek Professor of Computer Science

Similar researchers at New York University

• Joseph Bonneauh-41
• Nir Bitanskyh-29
• Marshall Ballh-11