Martín Farach-Colton

Publications

65 journal articles and 146 conference papers. Titles link to a free copy where one is available. Also on Google Scholar and dblp.

Journal Articles (65)

  1. History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion TreesM. A. Bender, M. Farach-Colton, M. T. Goodrich, H. KomlósTODS, 2026. Selected for Special Issue of ACM Transactions on Database Systems, Best of PODS 2024 doi
  2. Mitigating False Positives in Filters: to Adapt or to CacheM. A. Bender, R. Das, M. Farach-Colton, T. M. Mo, D. Tench, Y. P. WangTODS 51(3):17:1–17:32, 2026 doi
  3. Tiny PointersM. A. Bender, A. Conway, M. Farach-Colton, W. Kuszmaul, G. TagliaviniTALG 21(4):38:1–38:43, 2025. Selected for Special Issue for SODA 2023 doi
  4. Tight Bounds for Monotone Minimal Perfect HashingS. Assadi, M. Farach-Colton, W. KuszmaulTALG 21(4):36:1–36:23, 2025. Selected for Special Issue for SODA 2023 doi
  5. Paging and the Address-Translation ProblemM. A. Bender, A. Bhattacharjee, A. Conway, M. Farach-Colton, R. Johnson, S. Kannan, W. Kuszmaul, N. Mukherjee, D. E. Porter, G. Tagliavini, J. Vorobyeva, E. T. WestTALG 21(4):43:1–43:22, 2025 doi
  6. History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data StructuresM. A. Bender, M. Farach-Colton, M. T. Goodrich, H. KomlósSIGMOD Record 54(1):17–26, 2025. ACM SIGMOD Research Highlight Award doi
  7. Online List Labeling: Breaking the log² n BarrierM. A. Bender, A. Conway, M. Farach-Colton, H. Komlós, W. Kuszmaul, N. WeinSICOMP 54(5):S22–S60, 2025. Selected for Special Issue for FOCS 2022 doi
  8. Mosaic Pages: Big TLB Reach with Small PagesK. Gosakan, J. Han, W. Kuszmaul, I. Mubarek, N. Mukherjee, G. Tagliavini, E. T. West, M. A. Bender, A. Bhattacharjee, A. Conway, M. Farach-Colton, J. Gandhi, R. Johnson, S. Kannan, D. E. PorterIEEE Micro 44(4):52–59, 2024. Selected for IEEE Micro Top Picks
  9. GraphZeppelin: How to Find Connected Components (Even When Graphs Are Dense, Dynamic, and Massive)D. Tench, E. T. West, V. Zhang, M. A. Bender, A. Chowdhury, J. A. Dellas, M. Farach-Colton, T. Seip, K. ZhangTODS 49(3):9:1–9:31, 2024 doi
  10. Iceberg Hashing: Optimizing Many Hash-Table Criteria at OnceM. A. Bender, A. Conway, M. Farach-Colton, W. Kuszmaul, G. TagliaviniJACM 70(6):40:1–40:51, 2023 doi
  11. Using Advanced Data Structures to Enable Responsive Security MonitoringJ. Vorobyeva, D. DeLayo, M. A. Bender, M. Farach-Colton, P. Pandey, C. A. Phillips, S. Singh, E. D. Thomas, T. M. KroegerCluster Computing 25(4):2893–2914, 2022. Selected for Special Issue on “Innovating the Network for Data-Intensive Science”
  12. Timely Reporting of Heavy Hitters using External MemoryM. A. Bender, J. W. Berry, M. Farach-Colton, R. Johnson, T. M. Kroeger, P. Pandey, C. A. Phillips, S. SinghTODS 46(4):14:1–14:35, 2021. Selected for Special Issue of ACM Transactions on Database Systems, Best of SIGMOD 2020
  13. Dynamic Windows Scheduling with ReallocationM. Farach-Colton, K. Leal, M. A. Mosteiro, C. Thraves CaroJEA 26:1.11:1–1.11:19, 2021 doi
  14. External-Memory Dictionaries in the Affine and PDAM ModelsM. A. Bender, A. Conway, M. Farach-Colton, W. Jannen, Y. Jiao, R. Johnson, E. Knorr, S. McAllister, N. Mukherjee, P. Pandey, D. E. Porter, J. Yuan, Y. ZhanTOPC 8(3):15:1–15:20, 2021. Selected for Special Issue for SPAA 2019
  15. Copy-on-Abundant-Write for Nimble File System ClonesY. Zhan, A. Conway, Y. Jiao, N. Mukherjee, I. Groombridge, M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, D. E. Porter, J. YuanTOS 17(1):5:1–5:27, 2021. Selected for Special Section for USENIX FAST 2020
  16. Efficient directory mutations in a full-path indexed file systemY. Zhan, A. Conway, Y. Jiao, E. Knorr, M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, D. E. Porter, J. YuanTOS 14(3):22:1–22:27, 2018. Selected for Special Issue for USENIX FAST 2018 doi
  17. Writes Wrought Right, and Other Adventures in File System OptimizationJ. Yuan, Y. Zhan, W. Jannen, P. Pandey, A. Akshintala, K. Chandnani, P. Deo, Z. Kasheff, L. Walsh, M. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, D. E. PorterTOS 13(1):3:1–3:26, 2017. Selected for Special Issue for USENIX FAST 2016 doi
  18. Cost-Oblivious ReallocationM. A. Bender, M. Farach-Colton, S. Fekete, J. Fineman, S. GilbertTALG 13(3):38:1–38:20, 2017 doi
  19. Fault-Tolerant Aggregation: Flow Update Meets Mass DistributionP. S. Almeida, C. Baquero, M. Farach-Colton, P. Jesus, M. A. MosteiroDistrib. Comput. 30(4):281–291, 2017 doi
  20. 40 Years of Suffix TreesA. Apostolico, M. Crochemore, M. Farach-Colton, Z. Galil, S. MuthukrishnanCACM 59(4):66–73, 2016
  21. Exact Sublinear Binomial SamplingM. Farach-Colton and M.-T. TsaiAlgorithmica 73(4):637–651, 2015. Selected for Special Issue for ISAAC 2013
  22. Initializing Sensor Networks of Non-uniform Density in the Weak Sensor ModelM. Farach-Colton and M. A. MosteiroAlgorithmica 73(1):87–114, 2015
  23. BetrFS: A Right-Optimized Write-Optimized File SystemW. Jannen, J. Yuan, Y. Zhan, A. Akshintala, J. Esmet, Y. Jiao, A. Mittal, P. Pandey, P. Reddy, L. Walsh, M. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, D. E. PorterTOS 11(4):18:1–18:29, 2015. Selected for Special Issue for USENIX FAST 2015 doi
  24. Reallocation Problems in SchedulingM. A. Bender, M. Farach-Colton, S. Fekete, J. Fineman, S. GilbertAlgorithmica 73(2):389–409, 2015 doi
  25. Optimal Memory-aware Sensor Network GossipingM. Farach-Colton, A. Fernández-Anta, M. A. MosteiroTCS 472:60–80, 2013 doi
  26. Bootstrapping a Hop-optimal Network in the Weak Sensor ModelM. Farach-Colton, R. J. Fernandes, M. A. MosteiroTALG 5(4):37:1–37:30, 2009
  27. Fast and Compact Regular Expression MatchingP. Bille and M. Farach-ColtonTCS 409(3):486–496, 2008 doi
  28. Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and UltrametricsN. Alon, M. Bădoiu, E. Demaine, M. Farach-Colton, M. Hajiaghayi, A. SidiropoulosTALG 4(4):46:1–46:21, 2008
  29. Optimal spaced seeds for faster approximate string matchingM. Farach-Colton, G. Landau, C. Şahinalp, D. TsurJCSS 73(7):1035–1044, 2007 doi
  30. Insertion Sort is O(n log n)M. A. Bender, M. Farach-Colton, M. A. MosteiroToCS 39(3):391–397, 2006. Selected for Special Issue for FUN 2004 doi
  31. On the Complexity of Ordinal ClusteringM. Farach-Colton and R. ShahJ. Classif. 23(1):79–102, 2006
  32. All-Pairs Lowest Common Ancestors in Trees and Directed Acyclic GraphsM. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. SumazinJ. Algorithms 57(2):75–94, 2005
  33. Cache-Oblivious B-TreesM. A. Bender, E. Demaine, M. Farach-ColtonSICOMP 35(2):341–358, 2005
  34. Finding Frequent Items in Data StreamsM. Charikar, K. Chen, M. Farach-ColtonTCS 312(1):3–15, 2004 doi
  35. The Level Ancestor Problem SimplifiedM. A. Bender and M. Farach-ColtonTCS 321(1):5–12, 2004 doi
  36. Randomization, Rigor and Persuasiveness in ProofsC. Womack and M. FarachSynthese 134(1–2):71–84, 2003
  37. Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole GenomesV. Choi and M. Farach-ColtonGene 320:165–176, 2003 doi
  38. Fast, Fair and Frugal Bandwidth Allocation in ATM NetworksY. Bartal, M. Farach-Colton, S. Yooseph, L. ZhangAlgorithmica 33(3):272–286, 2002
  39. An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary TreesR. Cole, M. Farach-Colton, R. Hariharan, T. Przytycka, M. ThorupSICOMP 30(5):1385–1404, 2000
  40. On Local Register AllocationM. Farach-Colton and V. LiberatoreJ. Algorithms 37(1):37–65, 2000
  41. Notung: Dating gene duplications using gene family treesK. Chen, D. Durand, M. Farach-ColtonJCB 7(3–4):429–447, 2000
  42. On the Sorting-Complexity of Suffix Tree ConstructionM. Farach-Colton, P. Ferragina, S. MuthukrishnanJACM 47(6):987–1011, 2000 doi
  43. Efficient Algorithms for Inverting EvolutionM. Farach and S. KannanJACM 46(4):437–449, 1999 doi
  44. On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)R. Agarwala, V. Bafna, M. Farach, M. Paterson, M. ThorupSICOMP 28(3):1073–1085, 1999
  45. Optimal Parallel Two Dimensional Text Searching on a CREW PRAMA. Amir, G. Benson, M. FarachInf. Comput. 144(1):1–17, 1998 doi
  46. String Matching in Lempel-Ziv Compressed StringsM. Farach and M. ThorupAlgorithmica 20(4):388–404, 1998
  47. Optimal Parallel Randomized RenamingM. Farach and S. MuthukrishnanIPL 61(1):7–10, 1997
  48. Sparse Dynamic Programming for Evolutionary Tree ComparisonM. Farach and M. ThorupSICOMP 26(1):210–230, 1997
  49. Optimal Two Dimensional Compressed MatchingA. Amir, G. Benson, M. FarachJ. Algorithms 24(2):354–379, 1997
  50. Recognizing Circular Decomposable MetricsM. FarachJCB 4(2):157–162, 1997
  51. Local Rules for Protein Folding on the Triangular Lattice and Generalized Hydrophobicity in the HP ModelR. Agarwala, S. Batzoglou, V. Dančík, S. Decatur, M. Farach, S. Hannenhalli, S. Muthukrishnan, S. SkienaJCB 4(3):275–296, 1997
  52. Numerical Taxonomy on Data: Experimental ResultsJ. Cohen and M. FarachJCB 4(4):547–558, 1997
  53. Let Sleeping Files Lie: Pattern Matching in Z-compressed FilesA. Amir, G. Benson, M. FarachJCSS 52(2):299–307, 1996 doi
  54. On the Agreement of Many TreesM. Farach, T. Przytycka, M. ThorupIPL 55(6):297–301, 1995
  55. Fast Comparison of Evolutionary TreesM. Farach and M. ThorupInf. Comput. 123(1):29–37, 1995 doi
  56. Improved Dynamic Dictionary MatchingA. Amir, M. Farach, R. Idury, H. La Poutré, A. SchäfferInf. Comput. 119(2):258–282, 1995 doi
  57. Efficient 2-dimensional Approximate Matching of Half-rectangular FiguresA. Amir and M. FarachInf. Comput. 118(1):1–11, 1995 doi
  58. A Robust Model for Finding Optimal Evolutionary TreesM. Farach, S. Kannan, T. WarnowAlgorithmica 13(1–2):155–179, 1995. Special Issue on Computational Biology
  59. Alphabet Dependence in Parameterized MatchingA. Amir, M. Farach, S. MuthukrishnanIPL 49(3):111–115, 1994
  60. Dynamic Dictionary MatchingA. Amir, M. Farach, R. Giancarlo, Z. Galil, K. ParkJCSS 49(2):208–222, 1994 doi
  61. An Alphabet Independent Approach to Two Dimensional Pattern MatchingA. Amir, G. Benson, M. FarachSICOMP 23(2):313–323, 1994
  62. Two Dimensional Dictionary MatchingA. Amir and M. FarachIPL 44(5):233–239, 1992
  63. Optimal Superprimitivity Testing for StringsA. Apostolico, M. Farach, C. IliopoulosIPL 39(1):17–20, 1991
  64. Efficient Matching of Nonrectangular ShapesA. Amir and M. FarachAnn. Math. Artif. Intell. 4:211–224, 1991
  65. Generating Plausible Diagnostic Hypotheses with Self-processing Causal NetworksJ. Wald, M. Farach, M. Tagamets, J. ReggiaJ. Exp. Theor. Artif. Intell. 1(2):91–112, 1989

Conference Papers (146)

  1. Popcorning: Repurposing Write-Optimization Buffers for Faster QueriesP. Afshani, M. A. Bender, P. Bille, A. Conway, M. Farach-Colton, J. Fineman, M. T. Goodrich, I. Gørtz, J. Iacono, R. Johnson, H. Komlós, W. Kuszmaul, R. Silver, R. Tarjan, S. Tarnow, R. ZhouPODS '27
  2. Tight Bounds for Memory Allocation With and Without Request FragmentationM. A. Bender, A. Conway, M. Farach-Colton, H. Komlós, W. Kuszmaul, N. WeinSODA '27
  3. Fast Sparse α-Navigable Graph Construction with Improved Resource AugmentationA. Conway, L. Dhulipala, M. Farach-Colton, B. Landrum, C. Musco, Y. Shechter, T. Suel, R. WenSODA '27
  4. The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage EconomicallyM. A. Bender, P. Bille, M. Farach-Colton, J. Fineman, I. Gørtz, M. T. Goodrich, H. Komlós, B. C. Kuszmaul, W. Kuszmaul, R. Silver, T. Veldhuizen, R. ZhouSPAA '26. Outstanding Paper Award
  5. Fast Concurrent Primitives Despite ContentionM. A. Bender, G. Blelloch, M. Farach-Colton, R. Zhou, R. Johnson, R. Oshman, Y. HuSPAA '26 doi
  6. Greedy Open Addressing Revisited: Beyond Yao's Lower BoundA. Krapivin, M. Farach-Colton, W. KuszmaulSTOC '26
  7. Breadcrumb Filters: Fast Fully Featured FiltersA. Krapivin, A. Rangarajan, A. Conway, M. Farach-Colton, R. Johnson, P. PandeySIGMOD '26 doi
  8. Bounding the Fragmentation of B-Trees Subject to Batched InsertionsM. A. Bender, A. Bernstein, N. Cao, A. Conway, M. Farach-Colton, H. Komlós, Y. Shechter, N. WeinSIGMOD '26 doi
  9. Efficiently Constructing Sparse Navigable GraphsA. Conway, L. Dhulipala, M. Farach-Colton, R. Johnson, B. Landrum, C. Musco, Y. Shechter, T. Suel, R. WenSODA '26 doi
  10. Don't Melt Your Cache: Low-Associativity with Heat-SinkM. A. Bender, A. Conway, D. DeLayo, M. Farach-Colton, J. Han, R. Johnson, W. Kuszmaul, E. T. WestSPAA '25. Distinguished Paper Award. Invited for a presentation at IGAFIT Highlights of Algorithms (HALG) 2026 doi
  11. The Case for External Graph SketchingM. A. Bender, M. Farach-Colton, R. Jacob, H. Komlós, D. Tench, E. T. WestACDA '25 doi
  12. Exploring the Landscape of Distributed Graph SketchingD. Tench, E. T. West, K. Zhang, M. A. Bender, D. DeLayo, M. Farach-Colton, G. Gill, T. Seip, V. ZhangALENEX '25 doi
  13. History-Independent Concurrent Hash TablesH. Attiya, M. A. Bender, M. Farach-Colton, R. Oshman, N. SchillerSTOC '25 doi
  14. Adaptive Quotient FiltersR. Wen, H. McCoy, D. Tench, G. Tagliavini, M. A. Bender, A. Conway, M. Farach-Colton, R. Johnson, P. PandeySIGMOD '25 doi
  15. Optimal Bounds for Open Addressing Without ReorderingA. Krapivin, M. Farach-Colton, W. KuszmaulFOCS '24 doi
  16. Nearly Optimal List LabelingM. A. Bender, A. Conway, M. Farach-Colton, H. Komlós, M. Koucký, W. Kuszmaul, M. SaksFOCS '24 doi
  17. History-Independent Concurrent ObjectsH. Attiya, M. A. Bender, M. Farach-Colton, R. Oshman, N. SchillerPODC '24 doi
  18. A Nearly Quadratic Improvement for Memory ReallocationM. Farach-Colton, W. Kuszmaul, N. Sheffield, A. WestoverSPAA '24 doi
  19. Snake in Optimal Space and TimeP. Bille, M. Farach-Colton, I. Gørtz, I. van der HoogFUN '24 doi
  20. History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data StructuresM. A. Bender, M. Farach-Colton, M. T. Goodrich, H. KomlósPODS '24. Best Paper Award. ACM SIGMOD Research Highlight Award. Selected for Special Issue of ACM Transactions on Database Systems, Best of PODS 2024. Invited for a presentation at IGAFIT Highlights of Algorithms (HALG) 2026 doi
  21. Layered List LabelingM. A. Bender, A. Conway, M. Farach-Colton, H. Komlós, W. KuszmaulPODS '24 doi
  22. Beyond Bloom: A Tutorial on Future Feature-Rich FiltersP. Pandey, M. Farach-Colton, N. Dayan, H. ZhangSIGMOD '24 (Tutorial)
  23. Modern Hashing Made SimpleM. A. Bender, M. Farach-Colton, J. Kuszmaul, W. KuszmaulSOSA '24
  24. Graph Ranking and the Cost of Sybil DefenseG. Farach-Colton, M. Farach-Colton, L. A. Goldberg, H. Komlós, J. Lapinskas, R. Levi, M. Medina, M. A. MosteiroEC '23 doi
  25. An Associativity Threshold Phenomenon in Set-Associative CachesM. A. Bender, R. Das, M. Farach-Colton, G. TagliaviniSPAA '23 doi
  26. Optimal Uncoordinated Unique IDsP. Dillinger, M. Farach-Colton, G. Tagliavini, S. WalzerPODS '23 doi
  27. Mosaic Pages: Big TLB Reach with Small PagesK. Gosakan, J. Han, W. Kuszmaul, I. Mubarek, N. Mukherjee, G. Tagliavini, E. T. West, M. A. Bender, A. Bhattacharjee, A. Conway, M. Farach-Colton, J. Gandhi, R. Johnson, S. Kannan, D. E. PorterASPLOS '23. Distinguished Paper Award. Selected for IEEE Micro Top Picks doi
  28. Tight Bounds for Monotone Minimal Perfect HashingS. Assadi, M. Farach-Colton, W. KuszmaulSODA '23. Selected for Special Issue for SODA 2023 doi
  29. Tiny PointersM. A. Bender, A. Conway, M. Farach-Colton, W. Kuszmaul, G. TagliaviniSODA '23. Selected for Special Issue for SODA 2023 doi
  30. Analyzing and Implementing GPU Hash TablesM. A. Awad, S. Ashkiani, S. Porumbescu, M. Farach-Colton, J. D. OwensAPOCS '23
  31. IcebergHT: High Performance PMEM Hash Tables Through Stability and Low AssociativityP. Pandey, A. Conway, M. A. Bender, J. Durie, M. Farach-Colton, W. Kuszmaul, R. Johnson, G. TagliaviniSIGMOD '23 doi
  32. SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction PolicyA. Conway, M. Farach-Colton, R. JohnsonSIGMOD '23 doi
  33. Online List Labeling: Breaking the log² n BarrierM. A. Bender, A. Conway, M. Farach-Colton, H. Komlós, W. Kuszmaul, N. WeinFOCS '22. Selected for Special Issue for FOCS 2022. Invited for a presentation at IGAFIT Highlights of Algorithms (HALG) 2023 doi
  34. GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph StreamsD. Tench, E. T. West, V. Zhang, M. A. Bender, A. Chowdhury, J. A. Dellas, M. Farach-Colton, T. Seip, K. ZhangSIGMOD '22 doi
  35. On the Optimal Time/Space Tradeoff for Hash TablesM. A. Bender, M. Farach-Colton, J. Kuszmaul, W. Kuszmaul, M. LiuSTOC '22 doi
  36. A Compleat File System for Commodity SSDsY. Jiao, S. Bertron, S. Patel, L. Zeller, R. Bennett, N. Mukherjee, M. A. Bender, M. Condict, A. Conway, M. Farach-Colton, X. Ge, W. Jannen, R. Johnson, D. E. Porter, J. YuanEuroSys '22. Artifacts Available, Artifacts Functional, Results Reproducible Badges
  37. What Does Dynamic Optimality Mean in External Memory?M. A. Bender, M. Farach-Colton, W. KuszmaulITCS '22 doi
  38. Paging and the Address Translation ProblemM. A. Bender, A. Bhattacharjee, A. Conway, M. Farach-Colton, R. Johnson, S. Kannan, W. Kuszmaul, N. Mukherjee, D. E. Porter, G. Tagliavini, J. Vorobyeva, E. T. WestSPAA '21
  39. Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter DesignP. Pandey, A. Conway, J. Durie, M. A. Bender, M. Farach-Colton, R. JohnsonSIGMOD '21 doi
  40. Mitigating false positives in filters: to adapt or to cache?M. A. Bender, R. Das, M. Farach-Colton, T. M. Mo, M. WangAPOCS '20
  41. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value StoresA. Conway, A. Gupta, V. Chidambaram, M. Farach-Colton, R. P. Spillane, A. Tai, R. JohnsonATC '20
  42. Timely Reporting of Heavy Hitters using External MemoryM. A. Bender, J. W. Berry, M. Farach-Colton, R. Johnson, T. M. Kroeger, P. Pandey, C. A. Phillips, S. SinghSIGMOD '20. Selected for Special Issue of ACM Transactions on Database Systems, Best of SIGMOD 2020. Results Reproduced Badge doi
  43. How to Copy FilesY. Zhan, A. Conway, Y. Jiao, N. Mukherjee, I. Groombridge, M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, D. E. Porter, J. YuanFAST '20. Best Paper Award Finalist. Selected for Special Section for USENIX FAST 2020. Invited for a summary in USENIX ;login:
  44. Streaming Complexity of Spanning Tree ComputationY.-J. Chang, M. Farach-Colton, T.-S. Hsu, M.-T. TsaiSTACS '20 doi
  45. Flushing without CascadesM. A. Bender, R. Das, M. Farach-Colton, R. Johnson, W. KuszmaulSODA '20
  46. Syntactic Separation of Subset Satisfiability ProblemsE. Allender, M. Farach-Colton, M.-T. TsaiAPPROX '19 doi
  47. Filesystem Aging: It's more Usage than FullnessA. Conway, E. Knorr, Y. Jiao, M. A. Bender, W. Jannen, R. Johnson, D. E. Porter, M. Farach-ColtonHotStorage '19
  48. Small Refinements to the DAM Can Have Big Consequences for Data-Structure DesignM. A. Bender, A. Conway, M. Farach-Colton, W. Jannen, Y. Jiao, R. Johnson, E. Knorr, S. McAllister, N. Mukherjee, P. Pandey, D. E. Porter, J. Yuan, Y. ZhanSPAA '19. Selected for Special Issue for SPAA 2019 doi
  49. Achieving Optimal Backlog in Multi-Processor Cup GamesM. A. Bender, M. Farach-Colton, W. KuszmaulSTOC '19 doi
  50. Engineering a High-Performance GPU B-TreeM. A. Awad, S. Ashkiani, R. Johnson, M. Farach-Colton, J. D. OwensPPoPP '19 doi
  51. Optimal Ball RecyclingM. A. Bender, A. Conway, J. Christensen, M. Farach-Colton, R. Johnson, M.-T. TsaiSODA '19 doi
  52. Streaming Algorithms for Planar Convex HullsM. Farach-Colton, M. Li, M.-T. TsaiISAAC '18 doi
  53. Bloom Filters, Adaptivity, and the Dictionary ProblemM. A. Bender, M. Farach-Colton, M. Goswami, R. Johnson, S. McCauley, S. SinghFOCS '18 doi
  54. Optimal Hashing in External MemoryA. Conway, M. Farach-Colton, P. ShilaneICALP '18 doi
  55. A Dynamic Hash Table for the GPUS. Ashkiani, M. Farach-Colton, J. D. OwensIPDPS '18 doi
  56. Quotient Filters: Approximate Membership Queries on the GPUA. Geil, M. Farach-Colton, J. D. OwensIPDPS '18
  57. GPU LSM: A Dynamic Dictionary Data Structure for the GPUS. Ashkiani, S. Li, M. Farach-Colton, N. Amenta, J. D. OwensIPDPS '18 doi
  58. The Full Path to Full-Path IndexingY. Zhan, A. Conway, Y. Jiao, E. Knorr, M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, D. E. Porter, J. YuanFAST '18. Best Paper Award Finalist. Selected for Special Issue for USENIX FAST 2018
  59. Mind the GapM. Farach-ColtonFUN '18 (Invited Paper) doi
  60. Dictionaries RevisitedM. Farach-ColtonSEA '17 (Invited Paper) doi
  61. Write-Optimized Skip ListsM. A. Bender, M. Farach-Colton, R. Johnson, S. Mauras, T. Mayer, C. A. Phillips, H. XuPODS '17 doi
  62. File Systems Fated for Senescence? Nonsense, Says Science!A. Conway, A. Bakshi, Y. Jiao, W. Jannen, Y. Zhan, J. Yuan, M. A. Bender, R. Johnson, B. C. Kuszmaul, D. E. Porter, M. Farach-ColtonFAST '17. Invited for a special presentation at the SNIA Storage Developer Conference 2017. Invited for a summary in USENIX ;login:
  63. Cross-Referenced Dictionaries and the Limits of Write OptimizationP. Afshani, M. A. Bender, M. Farach-Colton, J. Fineman, M. Goswami, M.-T. TsaiSODA '17
  64. Parallel Lookups in String IndexesM. Farach-Colton and A. RoySPIRE '16
  65. Lazy Analytics: Let Other Queries Do the Work For YouW. Jannen, D. E. Porter, M. A. Bender, R. Johnson, B. C. Kuszmaul, M. Farach-ColtonHotStorage '16
  66. Optimizing Every Operation in a Write-Optimized File SystemJ. Yuan, Y. Zhan, W. Jannen, P. Pandey, A. Akshintala, K. Chandnani, P. Deo, Z. Kasheff, L. Walsh, M. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, D. E. PorterFAST '16. Best Paper Award. Best of the Rest Award, USENIX Annual Technical Conference 2016. Selected for Special Issue for USENIX FAST 2016. Invited for a special presentation at the SNIA Storage Developer Conference 2017
  67. The I/O Complexity of Computing Prime TablesM. A. Bender, R. Chowdhury, A. Conway, M. Farach-Colton, P. Ganapathi, R. Johnson, S. McCauley, B. Simon, S. SinghLATIN '16
  68. Tight Approximations of Graph Degeneracy in Large GraphsM. Farach-Colton and M.-T. TsaiLATIN '16
  69. On the Complexity of Computing Prime TablesM. Farach-Colton and M.-T. TsaiISAAC '15 doi
  70. Finding Articulation Points of Large Graphs in Linear TimeM. Farach-Colton, T.-S. Hsu, M. Li, M.-T. TsaiWADS '15
  71. Cost-Oblivious Reallocation for Scheduling and PlanningM. A. Bender, M. Farach-Colton, S. Fekete, J. Fineman, S. GilbertSPAA '15
  72. BetrFS: A Right-Optimized Write-Optimized File SystemW. Jannen, J. Yuan, Y. Zhan, A. Akshintala, J. Esmet, Y. Jiao, A. Mittal, P. Pandey, P. Reddy, L. Walsh, M. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, D. E. PorterFAST '15. Best Paper Award Finalist. Selected for Special Issue for USENIX FAST 2015
  73. The Batched Predecessor Problem in External MemoryM. A. Bender, M. Farach-Colton, M. Goswami, D. Medjedovic, P. Montes, M.-T. TsaiESA '14
  74. Dynamic Windows Scheduling with ReallocationsM. Farach-Colton, K. Leal, M. A. Mosteiro, C. Thraves CaroSEA '14 doi
  75. Cost-Oblivious Storage ReallocationM. A. Bender, M. Farach-Colton, S. Fekete, J. Fineman, S. GilbertPODS '14 doi
  76. Computing the Degeneracy of Large GraphsM. Farach-Colton and M.-T. TsaiLATIN '14
  77. Forty Years of Text IndexingA. Apostolico, M. Crochemore, M. Farach-Colton, Z. Galil, S. MuthukrishnanCPM '13
  78. Exact Sublinear Binomial SamplingM. Farach-Colton and M.-T. TsaiISAAC '13. Selected for Special Issue for ISAAC 2013
  79. Reallocation Problems in SchedulingM. A. Bender, M. Farach-Colton, S. Fekete, J. Fineman, S. GilbertSPAA '13 doi
  80. Don't Thrash: How to Cache Your Hash on FlashM. A. Bender, M. Farach-Colton, R. Johnson, R. Kraner, B. C. Kuszmaul, D. Medjedovic, P. Montes, P. Shetty, R. P. Spillane, E. ZadokVLDB '12 doi
  81. The TokuFS File SystemJ. Esmet, M. A. Bender, M. Farach-Colton, B. C. KuszmaulHotStorage '12
  82. Opportunistic Information Dissemination in Mobile Ad-hoc Networks: adaptiveness vs obliviousness and randomization vs determinismM. Farach-Colton, A. Fernández-Anta, A. Milani, M. A. Mosteiro, S. ZaksLATIN '12 doi
  83. Don't Thrash: How to Cache Your Hash on FlashM. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, D. Medjedovic, P. Montes, P. Shetty, R. P. Spillane, E. ZadokHotStorage '11
  84. Fault-Tolerant Aggregation: Flow Update Meets Mass DistributionP. S. Almeida, C. Baquero, M. Farach-Colton, P. Jesus, M. A. MosteiroOPODIS '11 doi
  85. Efficient and Robust Prediction Algorithms for Protein Complexes using Gomory-Hu TreeA. Mitrofanova, M. Farach-Colton, B. MishraPSB '09 doi
  86. A Linear Delay Algorithm for Building Concept LatticesM. Farach-Colton and Y. HuangCPM '08
  87. Sensor Network Gossiping or How to Break the Broadcast Lower BoundM. Farach-Colton and M. A. MosteiroISAAC '07
  88. Initializing Sensor Networks of Non-uniform Density in the Weak Sensor ModelM. Farach-Colton and M. A. MosteiroWADS '07
  89. Cache-Oblivious Streaming B-TreesM. A. Bender, M. Farach-Colton, J. Fineman, Y. Fogel, B. C. Kuszmaul, J. NelsonSPAA '07
  90. Lattice based clustering of temporal gene-expression matricesM. Farach-Colton and Y. HuangSDM '07
  91. Lower Bounds for Clear Transmissions in Radio NetworksM. Farach-Colton, R. J. Fernandes, M. A. MosteiroLATIN '06
  92. Cache-Oblivious String B-TreesM. A. Bender, M. Farach-Colton, B. C. KuszmaulPODS '06
  93. Bootstrapping a Hop-optimal Network in the Weak Sensor ModelM. Farach-Colton, R. J. Fernandes, M. A. MosteiroESA '05
  94. Adversarial Contention Resolution for Simple ChannelsM. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, C. E. LeisersonSPAA '05
  95. Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and UltrametricsN. Alon, M. Bădoiu, E. Demaine, M. Farach-Colton, M. Hajiaghayi, A. SidiropoulosSODA '05
  96. Optimal spaced seeds for faster approximate string matchingM. Farach-Colton, G. Landau, C. Şahinalp, D. TsurICALP '05
  97. Adversarial Analyses of Window Backoff StrategiesM. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, C. E. LeisersonIPDPS '04, NSF Next Generation Software Program PI Workshop
  98. Discovering Temporal Relations in Molecular Pathways Using Protein-Protein InteractionsM. Farach-Colton, Y. Huang, J. WoolfordRECOMB '04
  99. Insertion Sort is O(n log n)M. A. Bender, M. Farach-Colton, M. A. MosteiroFUN '04. Selected for Special Issue for FUN 2004
  100. Adventures at GoogleM. Farach-ColtonENC '03 (Invited Paper)
  101. The Level Ancestor Problem SimplifiedM. A. Bender and M. Farach-ColtonLATIN '02
  102. Two Simplified Algorithms for Maintaining Order in a ListM. A. Bender, R. Cole, E. Demaine, M. Farach-Colton, J. ZitoESA '02
  103. Scanning and Traversing: Maintaining Data for Traversals in a Memory HierarchyM. A. Bender, R. Cole, E. Demaine, M. Farach-ColtonESA '02
  104. Efficient Tree Layout in a Multilevel Memory HierarchyM. A. Bender, E. Demaine, M. Farach-ColtonESA '02 doi
  105. Finding Frequent Items in Data StreamsM. Charikar, K. Chen, M. Farach-ColtonICALP '02
  106. Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on TreesR. Shah and M. Farach-ColtonSODA '02
  107. Structure-based Feature Extraction from Protein DatabasesM. Farach-Colton and G. HristescuMETMBS '01
  108. On the Midpath Tree Conjecture: A Counter-ExampleM. Farach-Colton and R. ShahSODA '01
  109. COFE: A Scalable Method for Feature Extraction from Complex ObjectsM. Farach-Colton and G. HristescuDaWaK '00
  110. The LCA Problem RevisitedM. A. Bender and M. Farach-ColtonLATIN '00. Imre Simon Test of Time Award
  111. Notung: Dating gene duplications using gene family treesK. Chen, D. Durand, M. Farach-ColtonRECOMB '00
  112. Cache-Oblivious B-TreesM. A. Bender, E. Demaine, M. Farach-ColtonFOCS '00
  113. Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via EmbeddingsM. Farach-Colton and P. IndykFOCS '99
  114. Evaluation of Algorithms for Local Register AllocationM. Farach-Colton, U. Kremer, V. LiberatoreCC '99 doi
  115. Fast, Fair and Frugal Bandwidth Allocation in ATM NetworksY. Bartal, M. Farach-Colton, S. Yooseph, L. ZhangSODA '99
  116. Overcoming Memory Bottlenecks in Suffix Tree ConstructionM. Farach, P. Ferragina, S. MuthukrishnanFOCS '98
  117. On Local Register AllocationM. Farach-Colton and V. LiberatoreSODA '98
  118. Nearly Tight Bounds on the Learnability of EvolutionA. Ambainis, R. Desper, M. Farach, S. KannanFOCS '97
  119. Randomization, Rigor and Persuasiveness in ProofsC. Womack and M. FarachLogic and Mathematical Reasoning '97
  120. DNA Strand Separation Prediction: A Parallel ImplementationG. Hristescu, C. Benham, M. FarachPDPTA '97
  121. Group Testing Problems with Sequences in Experimental Molecular BiologyM. Farach, S. Kannan, E. Knill, S. MuthukrishnanSEQUENCES '97
  122. Optimal Suffix Tree Construction with Large AlphabetsM. FarachFOCS '97
  123. Numerical Taxonomy on Data: Experimental ResultsJ. Cohen and M. FarachSODA '97
  124. Local Rules for Protein Folding on the Triangular Lattice and Generalized Hydrophobicity in the HP ModelR. Agarwala, S. Batzoglou, V. Dančík, S. Decatur, M. Farach, S. Hannenhalli, S. Muthukrishnan, S. SkienaSODA '97
  125. Perfect Hashing for Strings: Formalization, Algorithms and Open ProblemsM. Farach and S. MuthukrishnanCPM '96
  126. The Structure of Circular Decomposable MetricsG. Christopher, M. Farach, M. TrickESA '96
  127. On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)R. Agarwala, V. Bafna, M. Farach, M. Paterson, M. ThorupSODA '96
  128. Efficient Algorithms for Inverting EvolutionM. Farach and S. KannanSTOC '96 doi
  129. Optimal Logarithmic Time Randomized Suffix Tree ConstructionM. Farach and S. MuthukrishnanICALP '96
  130. Computing the Agreement of Trees with Bounded DegreesM. Farach, T. Przytycka, M. ThorupESA '95
  131. Optimal Parallel Dictionary Matching and CompressionM. Farach and S. MuthukrishnanSPAA '95 doi
  132. On the Entropy of DNA: Algorithms and Measurements based on Memory and Rapid ConvergenceM. Farach, M. Noordewier, S. Savari, L. Shepp, A. Wyner, J. ZivSODA '95
  133. String Matching in Lempel-Ziv Compressed StringsM. Farach and M. ThorupSTOC '95 doi
  134. An Efficient Algorithm for Dynamic Text IndexingM. Gu., M. Farach, R. BeigelSODA '94
  135. Optimal Evolutionary Tree Comparison by Sparse Dynamic ProgrammingM. Farach and M. ThorupFOCS '94
  136. Let Sleeping Files Lie: Pattern Matching in Z-compressed FilesA. Amir, G. Benson, M. FarachSODA '94
  137. Fast Comparison of Evolutionary TreesM. Farach and M. ThorupSODA '94
  138. Optimal Two Dimensional Compressed MatchingA. Amir, G. Benson, M. FarachICALP '94
  139. A Robust Model for Finding Optimal Evolutionary TreesM. Farach, S. Kannan, T. WarnowSTOC '93
  140. Parallel Two Dimensional Pattern MatchingA. Amir, G. Benson, M. FarachSPAA '93
  141. Improved Dynamic Dictionary MatchingA. Amir, M. Farach, R. Idury, H. La Poutré, A. SchäfferSODA '93
  142. Efficient Randomized Dictionary Matching AlgorithmsA. Amir, M. Farach, Y. MatiasCPM '92
  143. Alphabet Independent Two Dimensional MatchingA. Amir, G. Benson, M. FarachSTOC '92 doi
  144. Adaptive Dictionary MatchingA. Amir and M. FarachFOCS '91
  145. Efficient 2-dimensional Approximate Matching of Non-rectangular FiguresA. Amir and M. FarachSODA '91
  146. The Whole is Faster than its PartsA. Amir and M. FarachFAI '89

Books, Chapters & Other (7)

  1. Y. Zhan, A. Conway, Y. Jiao, N. Mukherjee, I. Groombridge, M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, D. E. Porter, J. Yuan. How to Not Copy Files. In ;login:, '20
  2. A. Conway, A. Bakshi, Y. Jiao, W. Jannen, Y. Zhan, J. Yuan, M. A. Bender, R. Johnson, B. C. Kuszmaul, D. E. Porter, M. Farach-Colton. How to Fragment Your File System. In ;login:, '17
  3. M. Farach-Colton, Lowest Common Ancestors in Trees. In Encyclopedia of Algorithms, Springer Verlag. Ming-Yang Kao, editor, '16 link
  4. M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, B. C. Kuszmaul, D. E. Porter, J. Yuan, Y. Zhan. An Introduction to Bε-trees and Write-Optimization. In ;login:, '15
  5. D. Durand and M. Farach-Colton, On the Design of Optimization Criteria for Multiple Sequence Alignment. In Biological Evolution and Statistical Physics, Springer Verlag. Michael Lässig and Angelo Valleriani, editors, '02 link
  6. M. Farach, F. Roberts, M. Vingron, M. Waterman, Editors. Mathematical Support for Molecular Biology, DIMACS Book Series, '99 link
  7. A. Amir and M. Farach, Extensions of String Matching and Array Pattern Matching. In Pattern Matching Algorithms and Applications, A. Apostolico and Z. Galil, Editors, '97