Martin Farach-Colton

According to our database1, Martin Farach-Colton authored at least 162 papers between 1989 and 2018.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Optimal Ball Recycling.
CoRR, 2018

Optimal Hashing in External Memory.
CoRR, 2018

Closure Operators and Spam Resistance for PageRank.
CoRR, 2018

Quotient Filters: Approximate Membership Queries on the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

GPU LSM: A Dynamic Dictionary Data Structure for the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

A Dynamic Hash Table for the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

Optimal Hashing in External Memory.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Mind the Gap (Invited Paper).
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

The Full Path to Full-Path Indexing.
Proceedings of the 16th USENIX Conference on File and Storage Technologies, 2018

2017
Writes Wrought Right, and Other Adventures in File System Optimization.
TOS, 2017

Cost-Oblivious Storage Reallocation.
ACM Trans. Algorithms, 2017

Fault-tolerant aggregation: Flow-Updating meets Mass-Distribution.
Distributed Computing, 2017

Bloom Filters, Adaptivity, and the Dictionary Problem.
CoRR, 2017

A Dynamic Hash Table for the GPU.
CoRR, 2017

GPU LSM: A Dynamic Dictionary Data Structure for the GPU.
CoRR, 2017

Dictionaries Revisited.
Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

Cross-Referenced Dictionaries and the Limits of Write Optimization.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Write-Optimized Skip Lists.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

File Systems Fated for Senescence? Nonsense, Says Science!
Proceedings of the 15th USENIX Conference on File and Storage Technologies, 2017

2016
Lowest Common Ancestors in Trees.
Encyclopedia of Algorithms, 2016

Special issue in honor of the 60th birthday of Amihood Amir.
Theor. Comput. Sci., 2016

40 years of suffix trees.
Commun. ACM, 2016

Optimizing Every Operation in a Write-optimized File System.
Proceedings of the 2016 USENIX Annual Technical Conference, 2016

Parallel Lookups in String Indexes.
Proceedings of the String Processing and Information Retrieval, 2016

Tight Approximations of Degeneracy in Large Graphs.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

The I/O Complexity of Computing Prime Tables.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Lazy Analytics: Let Other Queries Do the Work For You.
Proceedings of the 8th USENIX Workshop on Hot Topics in Storage and File Systems, 2016

Optimizing Every Operation in a Write-optimized File System.
Proceedings of the 14th USENIX Conference on File and Storage Technologies, 2016

2015
BetrFS: Write-Optimization in a Kernel File System.
TOS, 2015

On the complexity of computing prime tables.
CoRR, 2015

Exact Sublinear Binomial Sampling.
Algorithmica, 2015

Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model.
Algorithmica, 2015

Reallocation Problems in Scheduling.
Algorithmica, 2015

Finding Articulation Points of Large Graphs in Linear Time.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Cost-Oblivious Reallocation for Scheduling and Planning.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

On the Complexity of Computing Prime Tables.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

BetrFS: A Right-Optimized Write-Optimized File System.
Proceedings of the 13th USENIX Conference on File and Storage Technologies, 2015

2014
Dynamic Windows Scheduling with Reallocation.
CoRR, 2014

Cost-oblivious storage reallocation.
CoRR, 2014

Dynamic Windows Scheduling with Reallocation.
Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Cost-oblivious storage reallocation.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Computing the Degeneracy of Large Graphs.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

The Batched Predecessor Problem in External Memory.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound).
Theor. Comput. Sci., 2013

Reallocation Problems in Scheduling
CoRR, 2013

Reallocation problems in scheduling.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Exact Sublinear Binomial Sampling.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Forty Years of Text Indexing.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012
Don't Thrash: How to Cache Your Hash on Flash.
PVLDB, 2012

Don't Thrash: How to Cache Your Hash on Flash
CoRR, 2012

Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

The TokuFS Streaming File System.
Proceedings of the 4th USENIX Workshop on Hot Topics in Storage and File Systems, 2012

2011
Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution
CoRR, 2011

Opportunistic Information Dissemination in Mobile Ad-hoc Networks: adaptiveness vs. obliviousness and randomization vs. determinism.
CoRR, 2011

Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: - Adaptiveness vs. Obliviousness and Randomization vs. Determinism.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution.
Proceedings of the Principles of Distributed Systems - 15th International Conference, 2011

Don't Thrash: How to Cache Your Hash on Flash.
Proceedings of the 3rd USENIX Workshop on Hot Topics in Storage and File Systems, 2011

2009
Bootstrapping a hop-optimal network in the weak sensor model.
ACM Trans. Algorithms, 2009

Efficient and Robust Prediction Algorithms for Protein Complexes Using Gomory-Hu Trees.
Proceedings of the Biocomputing 2009: Proceedings of the Pacific Symposium, 2009

2008
Fast and compact regular expression matching.
Theor. Comput. Sci., 2008

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Trans. Algorithms, 2008

A Linear Delay Algorithm for Building Concept Lattices.
Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007
Preface.
Theor. Comput. Sci., 2007

Introduction to SODA 2002 and 2003 special issue.
ACM Trans. Algorithms, 2007

Optimal spaced seeds for faster approximate string matching.
J. Comput. Syst. Sci., 2007

Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Cache-oblivious streaming B-trees.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Lattice based Clustering of Temporal Gene-Expression Matrices.
Proceedings of the Seventh SIAM International Conference on Data Mining, 2007

Sensor Network Gossiping or How to Break the Broadcast Lower Bound.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
Insertion Sort is O(n log n).
Theory Comput. Syst., 2006

On the Complexity of Ordinal Clustering.
J. Classification, 2006

Cache-oblivious string B-trees.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Lower Bounds for Clear Transmissions in Radio Networks.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005
Cache-Oblivious B-Trees.
SIAM J. Comput., 2005

Lowest common ancestors in trees and directed acyclic graphs.
J. Algorithms, 2005

Fast and Compact Regular Expression Matching
CoRR, 2005

Adversarial contention resolution for simple channels.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Optimal Spaced Seeds for Faster Approximate String Matching.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Bootstrapping a Hop-Optimal Network in the Weak Sensor Model.
Proceedings of the Algorithms, 2005

2004
Finding frequent items in data streams.
Theor. Comput. Sci., 2004

The Level Ancestor Problem simplified.
Theor. Comput. Sci., 2004

Insertion Sort is O(n log n)
CoRR, 2004

Discovering temporal relations in molecular pathways using protein-protein interactions.
Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Adversarial Analyses of Window Backoff Strategies.
Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004

2003
Randomization, Persuasiveness and Rigor in Proofs.
Synthese, 2003

Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes
CoRR, 2003

Adventures at Google.
Proceedings of the 4th Mexican International Conference on Computer Science (ENC 2003), 2003

2002
Efficient Tree Layout in a Multilevel Memory Hierarchy
CoRR, 2002

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.
Algorithmica, 2002

Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

The Level Ancestor Problem Simplified.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Finding Frequent Items in Data Streams.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy.
Proceedings of the Algorithms, 2002

Two Simplified Algorithms for Maintaining Order in a List.
Proceedings of the Algorithms, 2002

Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy.
Proceedings of the Algorithms, 2002

2001
On the midpath tree conjuncture: a counter-example.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
SIAM J. Comput., 2000

NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees.
Journal of Computational Biology, 2000

On Local Register Allocation.
J. Algorithms, 2000

On the sorting-complexity of suffix tree construction.
J. ACM, 2000

Notung: dating gene duplications using gene family trees.
Proceedings of the Fourth Annual International Conference on Computational Molecular Biology, 2000

The LCA Problem Revisited.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

Cache-Oblivious B-Trees.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

COFE: A Scalable Method for Feature Extraction from Complex Objects.
Proceedings of the Data Warehousing and Knowledge Discovery, 2000

1999
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
SIAM J. Comput., 1999

Efficient Algorithms for Inverting Evolution.
J. ACM, 1999

Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Evaluation of Algorithms for Local Register Allocation.
Proceedings of the Compiler Construction, 8th International Conference, 1999

1998
Optimal Parallel Two Dimensional Text Searching on a CREW PRAM.
Inf. Comput., 1998

String Matching in Lempel-Ziv Compressed Strings.
Algorithmica, 1998

On Local Register Allocation.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Overcoming the Memory Bottleneck in Suffix Tree Construction.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Sparse Dynamic Programming for Evolutionary-Tree Comparison.
SIAM J. Comput., 1997

Recognizing Circular Decompossible Metrics.
Journal of Computational Biology, 1997

Numerical Taxonomy on Data: Experimental Results.
Journal of Computational Biology, 1997

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model.
Journal of Computational Biology, 1997

Optimal Two-Dimensional Compressed Matching.
J. Algorithms, 1997

Optimal Parallel Randomized Renaming.
Inf. Process. Lett., 1997

Numerical Taxonomy on Data: Experimental Results.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Numerical taxonomy on data (abstract): experimental results.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

DNA Strand Separation Prediction: A Parallel Implementation.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1997

Optimal Suffix Tree Construction with Large Alphabets.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Nearly Tight Bounds on the Learnability of Evolution.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Two dimensional matching.
Proceedings of the Pattern Matching Algorithms, 1997

1996
Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files.
J. Comput. Syst. Sci., 1996

Efficient Algorithms for Inverting Evolution.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Optimal Logarithmic Time Randomized Suffix Tree Construction.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

The Structure of Circular Decomposable Metrics.
Proceedings of the Algorithms, 1996

Perfect Hashing for Strings: Formalization and Algorithms.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
Improved Dynamic Dictionary Matching
Inf. Comput., June, 1995

Efficient 2-Dimensional Approximate Matching of Half-Rectangular Figures
Inf. Comput., April, 1995

On the Agreement of Many Trees.
Inf. Process. Lett., 1995

Fast Comparison of Evolutionary Trees.
Inf. Comput., 1995

A Robust Model for Finding Optimal Evolutionary Trees.
Algorithmica, 1995

String matching in Lempel-Ziv compressed strings.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Optimal Parallel Dictionary Matching and Compression (Extended Abstract).
SPAA, 1995

On the Entropy of DNA: Algorithms and Measurements Based on Memory and Rapid Convergence.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Computing the Agreement of Trees with Bounded Degrees.
Proceedings of the Algorithms, 1995

1994
An Alphabet Independent Approach to Two-Dimensional Pattern Matching.
SIAM J. Comput., 1994

Dynamic Dictionary Matching.
J. Comput. Syst. Sci., 1994

Alphabet Dependence in Parameterized Matching.
Inf. Process. Lett., 1994

An Efficient Algorithm for Dynamic Text Indexing.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Fast Comparison of Evolutionary Trees.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Let Sleeping Files Lie: Pattern Matching in Z-compressed Files.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Optimal Two-Dimensional Compressed Matching.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
A robust model for finding optimal evolutionary trees.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Optimal Parallel Two Dimensional Pattern Matching.
SPAA, 1993

Improved Dynamic Dictionary Matching.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992
Two-Dimensional Dictionary Matching.
Inf. Process. Lett., 1992

Alphabet Independent Two Dimensional Matching
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Efficient Randomized Dictionary Matching Algorithms (Extended Abstract).
Proceedings of the Combinatorial Pattern Matching, Third Annual Symposium, 1992

1991
Optimal Superprimitivity Testing for Strings.
Inf. Process. Lett., 1991

Efficient matching of nonrectangular shapes.
Ann. Math. Artif. Intell., 1991

Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Adaptive Dictionary Matching
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1989
Generating plausible diagnostic hypotheses with self-processing causal networks.
J. Exp. Theor. Artif. Intell., 1989


  Loading...