Note: an internet scammer is sending emails spoofing my email address.
If you get any emails about internship offers (or other emails that seem off in some way), they aren't from me. They are from this scammer.

Monteverde Cloud Forest, Costa Rica
 

Michael A. Bender

John L. Hennessy Chaired Professor of Computer Science

Department of Computer Science
Stony Brook University
Stony Brook, NY 11794-2424 
USA
Tel.: +1 631-632-7835 
Fax: +1 631-632-8334 
E-mail: bender@cs.stonybrook.edu


Short Biography Vita Bibtex Files of Publications Company


Teaching Awards Program Committees Patents Journal Publications Conference Publications Selected Talks

Education

  • Harvard University.  PhD 1998 and SM 1995 in Computer Science.
    Advisor: M. Rabin.
    Thesis: New Algorithms and Metrics for Scheduling.
  • Ecole Normale Supérieure de Lyon, France.  Diplôme d'Etudes Approfondies (DEA) d'Informatique Fondamentale and Magistère d'Informatique et de Modelisation. Mention bien, 1993.
  • Harvard University. BA Magna Cum Laude with Highest Honors in Applied Mathematics, 1992.

    • Computer Science Honors Program

    Teaching

    Past Teaching

    Awards

    1. PODS Best Paper Award. ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2024.
    2. Fellow of the European Association of Theoretical Computer Science, 2023.
    3. ASPLOS Distinguished Paper Award, 2023.
    4. SPAA Best Paper Runner-up Award, 2022.
    5. USENIX FAST Best Paper Runner-up Award, 2018.
    6. USENIX FAST Best Paper Award, 2016.
    7. USENIX FAST Best Paper Runner-up Award, 2015.
    8. Chancellors Award for Excellence in Teaching, Stony Brook University, 2015.
    9. IPDPS Best Paper Award, 2015.
    10. Major Contributions to Graduate Education and Research, Dept of Computer Science, Stony Brook University, 2012.
    11. Imre Simon Test-of-Time Award, 2012.
    12. Undergraduate Teaching Award, Dept of Computer Science, Stony Brook University, 2006.
    13. R&D 100 Award for Compute Process Allocator, 2006. Joint award with V. J. Leung (Sandia Labs), D. P. Bunde (UIUC), K. Pedretti (Sandia Labs), C. A. Phillips (Sandia Labs).
    14. PODS Best Newcomer Award, 2006.
    15. Dean's Award for Excellence in Graduate Teaching by a Faculty Member, Stony Brook University, 2005.
    16. Graduate Teaching Award, Dept of Computer Science, Stony Brook University, 2000.

    Company

    Program Committees

    1. 10th Annual Fall Workshop on Computational Geometry 2000
    2. Genetic and Evolutionary Computation COnference (GECCO) 2001
    3. 1st International Workshop on Efficient Algorithms (WEA) 2001
    4. Latin American Theoretical INformatics (LATIN) 2002
    5. Genetic and Evolutionary Computation COnference (GECCO) 2002
    6. 5th Workshop on Algorithm Engineering and Experiments (ALENEX) 2003
    7. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003
    8. 10th International Conference on High Performance Computing (HiPC) 2003
    9. Latin American Theoretical INformatics (LATIN) 2004
    10. 3rd International Conference on FUN with Algorithms (FUN) 2004
    11. 11th International Conference on High Performance Computing (HiPC) 2004
    12. Genetic and Evolutionary Computation COnference (GECCO) 2004
    13. 15th Annual International Symposium on Algorithms and Computation (ISAAC) 2004
    14. 10th Annual International Computing and Combinatorics Conference (COCOON) 2004
    15. 13th Annual European Symposium on Algorithms (ESA) 2005
    16. 2nd Multidisciplinary International Conference on Scheduling (MISTA) 2005
    17. 12th International Conference on High Performance Computing (HiPC) 2005 (Vice-Chair, Algorithms Track)
    18. 11th European Conference on Parallel Processing (Euro-Par) 2005 (Vice-Chair, Scheduling and Load Balancing)
    19. 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2006
    20. 12th International Conference on Parallel and Distributed Systems (ICPADS), 2006
    21. 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2006
    22. 13th String Processing and Information Retrieval (SPIRE) 2006
    23. 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2007
    24. Workshop on Programming Models for Grid Computing (PMGC) 2007
    25. Latin American Theoretical Informatics (LATIN) 2008
    26. 9th Workshop on Algorithm Engineering and Experiments (ALENEX) 2008
    27. 35th International Colloquium on Automata, Languages, and Programming (ICALP) 2008
    28. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks 2008
    29. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2009 (Program Committee Chair)
    30. 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2010
    31. 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) 2010
    32. 17th International Conference on High Performance Computing (HiPC) 2010
    33. 31st International Conference on Distributed Computing Systems (ICDCS) 2011 (Vice Chair, Algorithms Track)
    34. 19th European Symposium on Algorithms (ESA), Engineering and Applications track
    35. 10th Latin American Theoretical Informatics (LATIN) 2012.
    36. 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2013.
    37. 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2013.
    38. ASE/IEEE International Conference on Big Data 2013.
    39. 11th Latin American Theoretical Informatics (LATIN) 2014.
    40. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015.
    41. 12th Latin American Theoretical Informatics (LATIN) 2016.
    42. 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2016.
    43. Eighth International Conference on Fun with Algorithms (FUN) 2016.
    44. 36th ACM SIGACT-SIGOPS Symposium on the Principles of Distributed Computing (PODC) 2017.
    45. 46th International Conference on Parallel Processing (ICPP) 2017. Algorithms Track Co-Chair.
    46. 13th Latin American Symposium on Theoretical INformatics (LATIN) 2018. PC Chair.
    47. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).
    48. 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) 2019.
    49. 27th Annual European Symposium on Algorithms (ESA) Track B, 2019. PC Chair.
    50. 23rd International Conference on Principles of Distributed Systems (OPODIS) 2019.
    51. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2020.
    52. 1st SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) 2021. PC Chair.
    53. 50th International Conference on Parallel Processing (ICPP) 2021.
    54. 35th International Symposium on Distributed Computing (DISC) 2021.
    55. 30th Annual European Symposium on Algorithms (ESA Track S) 2022.
    56. 37th IEEE International Parallel & Distributed Processing Symposium (IPDPS) 2023
    57. 2nd SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) 2023.
    58. 1st Workshop on Highlights of Parallel Computing (HOPC) 2023.

    Selected Conference Organization

    1. Publicity Chair. Symposium on Parallelism in Algorithms and Architectures (SPAA), 2000-2007.
    2. Co-organizer. Dagstuhl Seminar 04301: Cache-Oblivious and Cache-Aware Algorithms, July 18-23, 2004.
    3. Co-organizer. CIRM Center at Marseille-Luminy: Scheduling Algorithms for New Emerging Applications, May 29-June 2, 2006.
    4. Co-organizer. CIRM Center at Marseille-Luminy: New Challenges in Scheduling Theory, 2008.
    5. Program Committee Chair. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009.
    6. Co-organizer. Centre CNRS "La Villa Clythia," Frejus, France. New Challenges in Scheduling Theory, 2010.
    7. Co-organizer. 44th ACM Symposium on Theory of Computing (STOC), Tutorial on Algorithms for Memory-Sensitive Computing, 2012.
    8. Program Committee Chair (joint with Miguel Mosteiro). 13th Latin American Symposium on Theoretical INformatics (LATIN), 2018.
    9. Program Committee Chair Track B. 27th Annual European Symposium on Algorithms (ESA), 2019.
    10. Program Committee Chair (joint with J. Gilbert) 1st SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2021.
    11. Co-organizer. Centre CNRS ``Paul-Langevin'', Aussois, France. New Challenges in Scheduling Theory, May 2022.
    12. Co-organizer. Centre CNRS ``Paul-Langevin'', Aussois, France. 1st ACDA Workshop in Aussois, September, 2022.

    Selected Patents

    Refereed Journal Publications

    1. Michael A. Bender and Howard A. Stone. "An Integral Equation Approach to the Study of the Steady-State Current at Surface Microelectrodes." Journal of Electroanalytical Chemistry and Interfacial Chemistry, 351:29-55, 1993.
    2. Michael A. Bender, Michel Gastaldo, and Michel Morvan. "Parallel Interval Order Recognition and Construction of Interval Representations." Theoretical Computer Science, 143(1):73-91, 1995.
    3. Yonatan Aumann, Michael A. Bender, and Lisa Zhang. "Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems." Information and Computation, 139(1):1-16, 1997.
    4. Michael A. Bender and Chandra Chekuri. "Performance Guarantees for the TSP with a Parameterized Triangle Inequality." Information Processing Letters, 73:17-21, 2000.
    5. Mie Sato, Ingmar Bitter, Michael A. Bender, Arie E. Kaufman, and Masayuki Nakajima. "Tree-Structure Extraction Algorithm for Accurate and Robust Skeletons" (in Japanese). The Journal of the Institute of Image Information and Television Engineers, 2000.
    6. Chandra Chekuri and Michael A. Bender. "An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines." Journal of Algorithms, 41:212-224, 2001.
    7. Michael A. Bender and Dana Ron. "Testing Properties of Directed Graphs: Acyclicity and Connectivity." Random Structures and Algorithms, 20(2): 184-205, 2002.
    8. Matthew Andrews, Michael A. Bender, and Lisa Zhang. "New Algorithms for the Disk Scheduling Problem." Algorithmica, 32(2): 277-301, 2002.
    9. Michael A. Bender and Michael O. Rabin. "Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk." Theory of Computing Systems Special Issue on SPAA '00, 35: 289-304, 2002.
    10. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, and Salil P. Vadhan. "The Power of a Pebble: Exploring and Mapping Directed Graphs. Information and Computation, 176(1):1-21, 2002.
    11. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven Skiena. "The Lazy Bureaucrat Scheduling Problem." Information and Computation, 184 (1):129-146, 2003.
    12. Carl M. Bender, Michael A. Bender, Erik D. Demaine, and Sándor P. Fekete. "What Is the Optimal Shape of a City?" Journal of Physics A: Mathematical and General, 37(1):147-159, 2004.
      Journal of Physics A: Mathematical and General #1 Most Downloaded Article in 2004.
      See Kuro5him a popular description of this paper.
    13. Michael A. Bender and Martín Farach-Colton. "The Level Ancestor Problem Simplified." Theoretical Computer Science Special Issue on LATIN '02, 321(1):5-12, 2004.
    14. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven Skiena. "When Can You Fold a Map?" Computational Geometry: Theory and Applications (CGTA), 29(1):23-46, 2004. Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.
    15. Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender, and Joseph S. B. Mitchell. ""Theoretical and Experimental Analysis of Heuristics for the Freeze-Tag Robot Awakening Problem." IEEE Transactions on Robotics and Automation, 20(4):691-701, 2004.
    16. Michael A. Bender, S. Muthukrishnan, and Rajmohan Rajaraman. "Approximation Algorithms for Average Stretch Scheduling." Journal of Scheduling Special Issue on SODA 02, 7(3):195-222, 2004.
    17. Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. "A Locality-Preserving Cache-Oblivious Dynamic Dictionary." Journal of Algorithms, 3(2):115-136, 2004.
      Journal of Algorithms Hottest Article, #1 Most Downloaded for 2004.
    18. Michael A. Bender, Saurabh Sethia, and Steven Skiena. "Data Structures for Maintaining Set Partitions." Random Structures and Algorithms, 25:43-67, 2004.
    19. Yonatan Aumann and Michael A. Bender. "Efficient Low-Contention Asynchronous Consensus with the Value-Oblivious Adversary Scheduler." Distributed Computing, 17(3): 191-207, 2005.
    20. Michael A. Bender, Erik D. Demaine, and Martín Farach-Colton. "Cache-Oblivious B-Trees." SIAM Journal on Computing, 35(2):341-358, 2005.
    21. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. "Optimal Covering Tours with Turn Costs." SIAM Journal on Computing, 35(3): 531-566, 2005.
    22. Michael A. Bender, Martín Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin. "Lowest common ancestors in trees and directed acyclic graphs." Journal of Algorithms, 57(2): 75-94, 2005.
    23. Michael A. Bender, Martin Farach-Colton, and Miguel Mosteiro. "Insertion Sort is O(n log n)." Theory of Computing Systems, 39(3): 391-397, 2006. Special Issue on FUN '04. [PDF] [postscript] [talk]
    24. Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, and Martin Skutella. "The Freeze-Tag Problem: How to Wake Up a Swarm of Robots." Algorithmica, 46(2): 193-221, 2006. [PDF] [postscript]
    25. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. "Cache-Oblivious Priority Queue and Graph Algorithm Applications." SIAM Journal on Computing, 36(6): 1672-1695, 2007. [PDF] [postscript]
    26. Michael A. Bender, Bryan Bradley, Geetha Jagannathan, and Krishnan Pillaipakkamnatt. "Sum-of-Squares Heuristics for Bin Packing and Memory Allocation." ACM Journal of Experimental Algorithms, 12, 2007.
    27. Carl M. Bender and Michael A. Bender. "Optimal Shape of a Blob." Journal of Mathematical Physics, 2007. 48, 073518, 2007. [PDF] [postscript]
    28. Michael A. Bender and Haodong Hu. "An Adaptive Packed-Memory Array." Transactions on Database Systems Special Issue on PODS '06, 32(4): 2007. [PDF] [postscript] [talk]
    29. Michael A. Bender, Raphaël Clifford, and Kostas Tsichlas. "Scheduling Algorithms for Procrastinators." Journal of Scheduling, 11(2), 2008 [PDF] [postscript] [talk]
    30. Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Firas Swidan, Steven Skiena, and Firas Swidan. "Improved Bounds on Sorting with Length-Weighted Reversals." Journal of Computer and Systems Sciences, 74(5): 744-774, 2008.
    31. Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips. "Communication-Aware Processor Allocation for Supercomputers." Algorithmica Special Issue on WADS '05, 50(2): 279-298, 2008.
    32. Kunal Agrawal, Michael A. Bender, and Jeremy T. Fineman. "The Worst Page-Replacement Policy." Theory of Computing Systems, Special Issue on FUN '07, 44(2): 175-185, 2009. [PDF] [postscript]
    33. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, and Elias Vicari. "Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model." Theory of Computing Systems, Special Issue on SPAA '07, 47(4): 934-962, 2010. [PDF] [postscript]
    34. Michael A. Bender, Bradley C. Kuszmaul, Shang-Hua Teng, and Kebin Wang. "Optimal Cache-Oblivious Mesh Layouts." Theory of Computing Systems, 48(2): 269-296, 2011. [PDF] [postscript]
    35. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz. "The Cost of Cache-Oblivious Searching." Algorithmica, 61(2): 463-505, 2011. [PDF] [postscript]
    36. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk. "The Snowblower Problem." Computational Geometry, 44(8): 370-384, 2011. [PDF] [postscript]
    37. Michael A. Bender, Martín Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. "Don't Thrash: How to Cache Your Hash on Flash." PVLDB, 5(11):1627-1637, 2012. [PDF] [postscript]
    38. Michael A. Bender, Ritwik Bose, Rezaul Chowdhury, and Samuel McCauley. "The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye." Theory of Computing Systems Special Issue on FUN12, pages 1-16, 2014. [PDF] [postscript]
    39. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. "Reallocation Problems in Scheduling." Algorithmica, 73:389-409, 2015. [PDF] [postscript]
    40. William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. "BetrFS: Write-Optimization in a Kernel File System." Transactions on Storage--Special Issue on USENIX FAST 2015, 11(4): 18:1-18:29, 2015. [PDF] [postscript]
    41. Michael A. Bender, Sándor P. Fekete, Alexander Kröller, Vincenzo Liberatore, Joseph S.B. Mitchell, Valentin Polishchuk, and Jukka Suomela. "The Minimum Backlog Problem." Theoretical Computer Science, 605(9): 51-61, 2015. [PDF] [postscript]
    42. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. "A New Approach to Incremental Cycle Detection and Related Problems." ACM Transactions on Algorithms, 12(2), 14:1-14:22, 2016. [PDF] [postscript]
    43. Michael A. Bender, Roozbeh Ebrahimi, Haodong Hu, and Bradley C. Kuszmaul. "B-trees and Cache-Oblivious B-trees with Different-Sized Atomic Keys." Transactions on Database Systems, 41(3), 19:1-19:33, July 2016. [PDF] [postscript]
    44. Michael A. Bender, Jonathan W. Berry, Simon D. Hammond, K. Scott Hemmert, Samuel McCauley, Branden Moore, Benjamin Moseley, Cynthia A. Phillips, David S. Resnick, and Arun Rodrigues. "Two-level main memory co-design: Multi-threaded algorithmic primitives, analysis, and simulation." Journal of Parallel and Distributed Computing, 102: 213-228, 2017.
    45. Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. "Writes Wrought Right, and Other Adventures in File System Optimization." Transactions on Storage---Special Issue on USENIX FAST 2016, 13(1), 3:1-3:21, March 2017.
    46. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. "Cost-Oblivious Storage Reallocation." ACM Transactions on Algorithms, 13(3), Article 38, August 2017.
    47. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro. "deBGR: an efficient and near-exact representation of the weighted de Bruijn graph." Bioinformatics, 33 (14): i133-i141, July 2017. https://doi.org/10.1093/bioinformatics/btx261.
    48. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro. "Squeakr: an exact and approximate k-mer counting system." Bioinformatics, 34(4): 568-575, February 2018. https://doi.org/10.1093/bioinformatics/btx636.
    49. Michael A. Bender, Rezaul A. Chowdhury, Pramod Ganapathi, Samuel McCauley, and Yuan Tang. "The range 1 query (R1Q) problem." Theoretical Computer Science, 743: 130-147, September 2018. https://doi.org/10.1016/j.tcs.2015.12.040.
    50. Yang Zhan, Yizheng Jiao, Donald E. Porter, Alex Conway, Eric Knorr, Martín Farach-Colton, Michael A. Bender, Jun Yuan, William Jannen, and Rob Johnson. "Efficient Directory Mutations in a Full-Path-Indexed File System." Transactions on Storage, 14(3):22:1-22:27, November 2018.
    51. Prashant Pandey, Fatemeh Almodaresi, Michael A. Bender, and Michael Ferdman, Rob Johnson, and Rob Patro. "Mantis: A Fast, Small, and Exact Large-Scale Sequence-Search Index." Cell Systems, 7(2), 201-207.E4, August 2018. http://dx.doi.org/10.1016/j.cels.2018.05.021
    52. Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. "Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses." SIAM Journal on Computing, 47(5): 1735-1754, October 2018. https://doi.org/10.1137/17M1158604.
    53. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. "Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness." Journal of the ACM, 66(1): 6:1-6:33, January 2019. http://doi.acm.org/10.1145/3276769
    54. Yang Zhan, Alex Conway, Yizheng Jiao, Nirjhar Mukherjee, Ian Groombridge, Michael A. Bender, Martín Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, and Jun Yuan. "Copy-on-Abundant-Write for Nimble File System Clones," ACM Transactions on Storage 17(1), Article no. 5, January 2021. https://dl.acm.org/doi/abs/10.1145/3423495.
    55. Michael A. Bender, Alex Conway, Martín Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan, and Yang Zhan. "External-Memory Dictionaries in the Affine and PDAM Models." ACM Transactions on Parallel Computing, 15:1-15:20, 2021. https://doi.org/10.1145/3470635.
    56. Shikha Singh*, Prashant Pandey*, Michael A. Bender, Jonathan W. Berry, Martín Farach-Colton, Rob Johnson, Thomas M. Kroeger, and Cynthia A. Phillips. "Timely Reporting of Heavy Hitters using External Memory." ACM Transactions on Database Systems, 46(4): 14:1-14:35, 2021.   *Joint first authors. https://doi.org/10.1145/3472392.
    57. Janet Vorobyeva*, Daniel R. Delayo*, Michael A. Bender, Martín Farach-Colton, Prashant Pandey, Cynthia A. Phillips, Shikha Singh, Eric D. Thomas, and Thomas M. Kroeger. "Using advanced data structures to enable responsive security monitoring." Cluster Computing, January 2022.   *Joint first authors. https://doi.org/10.1007/s10586-021-03463-5.
    58. Prashant Pandey, Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini, and Rob Johnson. "IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity." ACM Management of Data (PACMMOD) and Proceedings of the ACM International Conference on Management of Data (SIGMOD), 1(1), 47:1--47:26, June 2023. https://dl.acm.org/doi/abs/10.1145/3588727.
    59. Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, and Guido Tagliavini. "Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once." Journal of the ACM, 40:1-40:51, October 2023. https://dl.acm.org/doi/10.1145/3625817.
    60. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein. "Online List Labeling: Breaking the $\log^2 n$ Barrier." SIAM Journal on Computing, Special Issue on FOCS, 2024. https://doi.org/10.1137/22M1534468.
    61. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, and William Kuszmaul. "Layered List Labeling." ACM Management of Data (PACMMOD)/47th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2(2), Article 101: pages 1-19, May 2024. https://doi.org/10.1145/3651602.
    62. Michael A. Bender, Martín Farach-Colton, Michael T. Goodrich, and Hanna Komlós. "History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures." ACM Management of Data (PACMMOD)/47th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2(2), Article 108: 1--19, May 2024. PODS Best Paper Award. https://doi.org/10.1145/3651609.
    63. Krishnan Gosakan, Jaehyun Han, William Kuszmaul, Ibrahim N. Mubarek, Nirjhar Mukherjee, Karthik Sriram, Guido Tagliavini, Evan West, Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martín Farach-Colton, Jayneel Gandhi, Rob Johnson, Sudarsan Kannan, and Donald E. Porter. "Mosaic Pages: Big TLB Reach with Small Pages." IEEE Micro, 2024. IEEE Micro Top Picks. https://doi.org/10.1109/MM.2024.3409181.
    64. Richard Wen, Hunter McCoy, David Tench, Guido Tagliavini, Michael A. Bender, Alex Conway, Martín Farach-Colton, Rob Johnson, and Prashant Panday. "Adaptive Quotient Filters." ACM Management of Data (PACMMOD)/Proc. ACM International Conference on Management of Data (SIGMOD), June 2025. Accepted.
    65. David Tench, Evan West, Victor Zhang, Michael A. Bender, Abiyazn Chowdhury, Daniel Delayo, J. Ahmed Dellas, Martin Farach-Colton, Tyler Seip, and Kenny Zhang. "GraphZeppelin: How to Find Connected Components (Even When Graphs Are Dense, Dynamic, and Massive)." Transactions on Database Systems, 2024. Accepted.
    66. Michael A. Bender, Alex Conway, Martín Farach-Colton, and William Kuszmaul. "Tiny Pointers." Transactions on Algorithms (TALG), Special Issue on SODA'23, 2024. Accepted.

    Refereed Conference Publications

    1. Michael A. Bender and Donna K. Slonim. "The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs." Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 75-85, 1994.
    2. Yonatan Aumann and Michael A. Bender. "Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler." Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 622-633, 1996.
    3. Matthew Andrews, Michael A. Bender, and Lisa Zhang. "New Algorithms for the Disk Scheduling Problem." Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 580-589, 1996.
    4. Yonatan Aumann, Michael A. Bender, and Lisa Zhang. "Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems." Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 270-276, 1996.
    5. Yonatan Aumann and Michael A. Bender. "Fault Tolerant Data Structures." Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 580-589, 1996.
    6. Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. "Flow and Stretch Metrics for Scheduling Continuous Job Streams." Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270-279, 1998.
    7. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, and Salil P. Vadhan. "The Power of a Pebble: Exploring and Mapping Directed Graphs." Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 269-278, 1998.
    8. Chandra Chekuri and Michael A. Bender. "An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines." Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 383-393. 1998.
    9. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven Skiena. "The Lazy Bureaucrat Scheduling Problem." Proceedings of the 6th Workshop on Discrete Algorithms (WADS), pages 80-85, 1999.
    10. Michael A. Bender and Chandra Chekuri. "Performance Guarantees for the TSP with a Parameterized Triangle Inequality." Proceedings of the 6th Workshop on Discrete Algorithms (WADS), pages 122-133, 1999.
    11. Michael A. Bender and Martín Farach-Colton. "The LCA Problem Revisited." LATIN, pages 88-94, 2000. [PDF] [postscript] [talk]
    12. Michael A. Bender, Saurabh Sethia, and Steven Skiena. "Data Structures for Maintaining Set Partitions." Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT), pages 83-96, 2000.
    13. Michael A. Bender and Dana Ron. "Testing Acyclicity of Directed Graphs in Sublinear Time." Proceedings of the 27th International Colloquium on Automata, Languages, and Programming (ICALP), pages 809-820, 2000.
    14. Michael A. Bender and Michael O. Rabin. "Scheduling Cilk Multithreaded Parallel Programs on Processors of Different Speeds." Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 13-21, 2000.
    15. Ingmar Bitter, Mie Sato, Michael A. Bender, Kevin T. McDonnell, Arie E. Kaufman, and Min Wan. "CEASAR: A Smooth, Accurate, and Robust Centerline Extraction Algorithm." IEEE Visualization 2000, pages 45-52, October 2000.
    16. Mie Sato, Ingmar Bitter, Michael A. Bender, and Arie E. Kaufman. "TEASAR: Tree-Structure Extraction Algorithm for Accurate and Robust Skeletons." Proceedings of the 8th Pacific Conference on Computer Graphics and Applications Graphics, pages 281-287, 2000.
    17. Michael A. Bender, Erik D. Demaine, and Martín Farach-Colton. "Cache-Oblivious B-Trees." Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 399-409, 2000.
    18. E. M. Arkin, M. A. Bender, E. D. Demaine, Sándor P. Fekete, J. S. B. Mitchell, and S. Sethia. "Optimal Covering Tours with Turn Costs." Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 138-147, 2001.
    19. Michael A. Bender, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. "Least Common Ancestors in Directed Acyclic Graphs." Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 845-854, 2001.
    20. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven Skiena. "When Can You Fold a Map?" Proceedings of the 7th Workshop on Discrete Algorithms (WADS), pages 401-413, 2001.
    21. Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, and Martin Skutella. "The Freeze-Tag Problem:  How to Wake Up a Swarm of Robots." Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568-577, 2002.
    22. Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. "A Locality-Preserving Cache-Oblivious Dynamic Dictionary." Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 29-38, 2002.
    23. Michael A. Bender, S. Muthukrishnan, and Rajmohan Rajaraman. "Improved Algorithms for Stretch Scheduling." Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 762-771, 2002.
    24. Michael A. Bender and Martín Farach-Colton. "The Level Ancestor Problem Simplified." LATIN, pages 508-515, 2002. Imre Simon Test-of-Time Award.
    25. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. "Cache-Oblivious Priority Queue and Graph Algorithm Applications." Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 268-276, 2002.
    26. Michael A. Bender, Richard Cole, and Rajeev Raman. "Exponential Structures for Cache-Oblivious Algorithms." Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002.
    27. Marcelo Sztainberg, Esther M. Arkin, Michael A. Bender, and Joseph S. B. Mitchell. "Analysis of Heuristics for the Freeze-Tag Problem." Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), pages 270-279, 2002.
    28. Michael A. Bender, Richard Cole, Erik D. Demaine, and Martín Farach-Colton. "Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 139-151, 2002.
    29. Michael A. Bender, Richard Cole, Erik D. Demaine, Martín Farach-Colton, and Jack Zito. "Two Simplified Algorithms for Maintaining Order in a List." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 152-164, 2002.
    30. Michael A. Bender, Erik D. Demaine, and Marin Farach-Colton. "Efficient Tree Layout in a Multilevel Memory Hierarchy." Proceedings of the 10th European Symposium on Algorithms (ESA), pages 165-173, 2002. Full Version.
    31. Vitus J. Leung, Esther M. Arkin, Michael A. Bender, David P. Bunde, Jeanette Johnston, Alok Lal, Joseph S. B. Mitchell, Cynthia A. Phillips, and Steven S. Seiden. "Processor Allocation on Cplant: Achieving General Processor Locality Using One-Dimensional Allocation Strategies." Proceedings of the 4th IEEE International Conference on Cluster Computing (CLUSTER), pages 296-304, 2002. Full Version as Sandia Report SAND2002-1488.
    32. Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, and Joseph S. B. Mitchell. "Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments." Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR), 77-94, 2002.
    33. Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, and Joseph S. B. Mitchell. "Online Dispersion Algorithms for Swarms of Robots." Proceedings of the 19th Annual ACM Symposium on Computational Geometry (SoCG), Video/DVD, pp. 382-383, 2003. [MPEG-1] [QuickTime] [Windows Media]
    34. Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He, and Joseph S. B. Mitchell. "Improved Approximation Algorithms for the Freeze-Tag Problem." Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 295-303, 2003.
    35. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz. "The Cost of Cache-Oblivious Searching." Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), pages 271-280, 2003.
    36. Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, and Firas Swidan. "Improved Bounds on Sorting with Length-Weighted Reversals." Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 912-921, 2004.
    37. Michael A. Bender, Bryan Bradley, Geetha Jagannathan, and Krishnan Pillaipakkamnatt. "The Robustness of the Sum-of-Squares Algorithm for Bin Packing." Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX), 2004.
    38. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson. "On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs." Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 133-144, 2004.
    39. Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro. "Insertion Sort is O(n log n)." Proceedings of the 3rd International Conference on Fun with Algorithms (FUN), pages 16-23, 2004.
    40. Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, and Ron Y. Pinter. "Sorting by Length-Weighted Reversals: Dealing with Signs and Circularity." Proceedings of the 15th Annual Combinatorial Pattern Matching Symposium (CPM), volume 3109 of Lecture Notes in Computer Science, pages 32-46, 2004.
    41. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul. "Concurrent Cache-Oblivious B-Trees." Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 228-237, 2005.
    42. Michael A. Bender, Martín Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. "Adversarial Contention Resolution for Simple Channels." Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325-332, 2005.
    43. Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips. "Communication-Aware Processor Allocation for Supercomputers." Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS), pages 169-181, 2005. [PDF] [postscript]
    44. Michael A. Bender and Haodong Hu. "An Adaptive Packed-Memory Array." Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 20-29, 2006. Best Newcomer Award. [PDF] [postscript] [talk]
    45. Michael A. Bender, Martín Farach-Colton, and Bradley C. Kuszmaul. "Cache-Oblivious String B-Trees." Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 233-242 2006. [PDF] [postscript]
    46. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk. "The Snowblower Problem." Proceedings of the 7th Workshop on Algorithmic Foundations of Robotics (WAFR), 2006. [PDF] [postscript] [talk]
    47. Michael A. Bender, Jeremey T. Fineman, and Seth Gilbert. "Contention Resolution with Heterogeneous Job Sizes." Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 112-123, 2006. [PDF] [postscript]
    48. Michael A. Bender and Cynthia A. Phillips. "Scheduling DAGs on Asynchronous Processors." Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 35-45, 2007. [PDF] [postscript] [talk]
    49. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, and Elias Vicari. "Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model." Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 61-70, 2007. [PDF] [postscript]
    50. Michael A. Bender, Martín Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley C. Kuszmaul, and Jelani Nelson. "Cache-Oblivious Streaming B-Trees." Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 81-92, 2007. [PDF] [postscript]
    51. Kunal Agrawal, Michael A. Bender, and Jeremy T. Fineman. "The Worst Page-Replacement Policy." Proceedings of the 4th International Conference on Fun With Algorithms (FUN), pages 135-145, 2007. [PDF] [postscript]
    52. Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert. "A New Approach to Incremental Topological Ordering." Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1108-1115, 2009. [PDF] [postscript]
    53. Michael A. Bender, Sándor P. Fekete, Tom Kamphans, and Nils Schweer. "Maintaining Arrays of Contiguous Objects." Proceedings of the 17th International Symposium on the Fundamentals of Computation Theory (FCT), LLNCS Volume 6599, pages 14-25, 2009. [PDF] [postscript]
    54. Michael A. Bender, Haodong Hu, and Bradley C. Kuszmaul. "Performance Guarantees for B-trees with Different-Sized Atomic Keys" Proceedings of the 29th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 305-316, 2010. [PDF] [postscript] [talk]
    55. Michael A. Bender, Martín Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. "Don't Thrash: How to Cache Your Hash on Flash." Proceedings of the 3rd USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2011. [PDF] [postscript] [talk]
    56. Michael A. Bender and Seth Gilbert. "Mutual Exclusion with O(log^2 log n) Amortized Work." Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 728-737, 2011. [PDF] [postscript] [talk]
    57. Michael A. Bender, Ritwik Bose, Rezaul Chowdhury, and Samuel McCauley. "The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye." Proceedings of the Sixth International Conference on Fun with Algorithms (FUN), pages 28-39, 2012. [PDF] [postscript]
    58. John Esmet, Michael A. Bender, Martín Farach-Colton, and Bradley C. Kuszmaul. "The TokuFS Streaming File System." Proceedings of the 4th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2012. [PDF] [postscript]
    59. Dan Alistarh, Michael A. Bender, Seth Gilbert, and Rachid Guerraoui. "How to Allocate Tasks Asynchronously." Proceedings of the 53nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012. [PDF] [postscript]
    60. Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. "Reallocation Problems in Scheduling." Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 271-279, 2013. [PDF] [postscript]
    61. Michael A. Bender, David P. Bunde, Vitus J. Leung, Samuel McCauley, and Cynthia A. Phillips. "Efficient Scheduling to Minimize Calibrations." Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 280-287, 2013. [PDF] [postscript]
    62. Dan Alistarh, James Aspnes, Michael A. Bender, Rati Gelashvili, and Seth Gilbert. "Dynamic Task Allocation in Asynchronous Shared Memory." Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 416-435, 2014. [PDF] [postscript]
    63. Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 958-971, 2014. [PDF] [postscript]
    64. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. "Cost-Oblivious Storage Reallocation." Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 278-288, 2014. [PDF] [postscript] [talk]
    65. Michael A. Bender, Rezaul Chowdhury, Pramod Ganapathi, Samuel McCauley, and Yuan Tang. "The Range 1 Query (R1Q) Problem." Proceedings of the 20th International Computing and Combinatorics Conference (COCOON), pages 116-128, 2014. [PDF] [postscript]
    66. Michael A. Bender, Martín Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes, and Meng-Tsung Tsai. "The Batched Predecessor Problem in External Memory." Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), pages 112-124, 2014. [PDF] [postscript]
    67. William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael Bender, Martín Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. "BetrFS: A Right-Optimized Write-Optimized File System." Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST), pages 301-315, 2015. [PDF] [postscript] [talk]
    68. Michael A. Bender, Jonathan Berry, Simon D. Hammond, K. Scott Hemmert, Samuel McCauley, Branden Moore, Benjamin Moseley, Cynthia A. Phillips, David Resnick, and Arun Rodrigues. "Two-Level Main Memory Co-Design: Multi-Threaded Algorithmic Primitives, Analysis, and Simulation." Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2015. Best Paper Award. [PDF] [postscript]
    69. Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. "Cost-Oblivious Reallocation for Scheduling and Planning." Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 143-154, 2015. [PDF] [postscript]
    70. Michael A. Bender, Jonathan Berry, Simon D. Hammond, Branden Moore, Benjamin Moseley, and Cynthia A. Phillips. "k-Means Clustering on Two-Level Memory Systems." Proceedings of the 26th International Symposium on Memory Systems (MEMSYS), pages 197-205, 2015. [PDF] [postscript]
    71. Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh, and Hoa T. Vu. "Run Generation Revisited: What Goes Up May or May Not Come Down." Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), pages 703-714, 2015. [PDF] [postscript]
    72. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. "How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness." Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 636-654, 2016. [PDF] [postscript]
    73. Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. "Optimizing Every Operation in a Write-Optimized File System." Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST), pages 1-14, 2016. Best Paper Award. [PDF] [postscript]
    74. Michael A. Bender, Rezaul Chowdhury, Alex Conway, Martín Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, and Shikha Singh. "The I/O Complexity of Computing Prime Tables." Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), pages 192-206, 2016. [PDF] [postscript]
    75. Michael A. Bender, Samuel McCauley, Bertrand Simon, Shikha Singh, and Frédéric Vivien. "Resource Optimization for Program Committee Members: A Subreview Article." Proceedings of the Eighth International Conference on Fun with Algorithms (FUN), pages 7:1-7:20, 2016, 2016. [PDF] [postscript]
    76. Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. "Contention Resolution with Log-Logstar Channel Accesses." Proceedings of the 48th Annual Symposium on the Theory of Computing (STOC), pages 499-508, 2016. [PDF] [postscript]
    77. William Jannen, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. "Lazy Analytics: Let Other Queries Do the Work For You." Proceedings of the 8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2016. [PDF] [postscript]
    78. Michael A. Bender, Jon Berry, Rob Johnson, Thomas M. Kroeger, Samuel McCauley, Cynthia A. Phillips, Bertrand Simon, Shikha Singh, and David Zage. "Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries." Proceedings of the 35th ACM Symposium on Principles of Database Systems (PODS), pages 289-302, 2016. [PDF] [postscript] [talk]
    79. Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, and Samuel McCauley. "Cache-Adaptive Analysis." Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 135-144, 2016. [PDF] [postscript] [talk]
    80. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes. "File Maintenance: When in Doubt, Change the Layout!" Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1503-1522, January 2017.
    81. Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, and Meng-Tsung Tsai. "Cross-Referenced Dictionaries and the Limits of Write Optimization." Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1523-1532, January 2017.
    82. Alexander Conway, Ainesh Bakshi, Yizheng Jiao, Yang Zhan, Michael A. Bender, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Martin Farach-Colton. "File Systems Fated for Senescence? Nonsense, Says Science!" Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST), pages 45-58, February 2017.
    83. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro. "A General-Purpose Counting Filter: Making Every Bit Count." Proceedings of the 2017 International Conference on Management of Data (SIGMOD), pages 775-787, May 2017.
    84. Michael A. Bender, Martin Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia Phillips, and Helen Xu. "Write-Optimized Skip Lists." Proceedings of the 36th ACM Symposium on Principles of Database Systems (PODS), pages 69-78, May 2017.
    85. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro. "An Efficient and Near-Exact Representation of the Weighted de Bruijn Graph." Proceedings of the Intelligent Systems in Molecular Biology (ISMB/ECCB), July 2017.
    86. Yang Zhan, Alexander Conway, Yizheng Jiao, Eric Knorr, Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, and Jun Yuan. "The Full Path to Full-Path Indexing." Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST), pages 123-138, February 2018.
    87. Michael A. Bender, Martín Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. "Bloom filters, adaptivity, and the dictionary problem." Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 182-193, October 2018.
    88. Michael A. Bender, Jake Christensen, Alex Conway, Martín Farach-Colton, Rob Johnson, and Meng-Tsung Tsai. "Optimal Ball Recycling." Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2527-2546, January 2019.
    89. Michael A. Bender, Alex Conway, Martín Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan, and Yang Zhan. "Small Refinements to the DAM Can Have Big Consequences for Data-Structure Design." Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 265-274, June 2019.
    90. Michael A. Bender, Martín Farach-Colton, and William Kuszmaul. "Achieving Optimal Backlog in Multi-Processor Cup Games." Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC), pages 1148-1157, June 2019.
    91. Alex Conway, Eric Knorr, Yizheng Jiao, Michael A. Bender, William Jannen, Rob Johnson, Donald E. Porter, and Martín Farach-Colton. "Filesystem Aging: It's more Usage than Fullness." Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), July 2019.
    92. Michael A. Bender, Rathish Das, Rob Johnson, Martín Karachi-Colton, and William Kuszmaul. "Flushing without Cascades." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 650-669, January 2020.
    93. Yang Zhan, Alexander Conway, Yizheng Jiao, Nirjhar Mukherjee, Ian Groombridge, Michael A. Bender, Martín Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, and Jun Yuan. "How to Copy Files." Proceedings of the 20th USENIX Conference on File and Storage Technologies (FAST), pages 75-89, February 2020.
    94. Shikha Singh, Sergey Madaminov, Michael A. Bender, Michael Ferdman, Ryan Johnson, Benjamin Moseley, Hung Ngo, Dung Nguyen, Soeren Olesen, Kurt Stirewalt, and Geoffrey Washburn. "A Scheduling Approach to Incremental Maintenance of Datalog Programs." Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 864-873, May 2020.
    95. Michael A. Bender, Mayank Goswami, Dzejla Medjedovic, Pablo Montes, and Kostas Tsichlas. "Batched Predecessor and Sorting with Size-Priced Information in External Memory." Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN), pages 155-167, 2020.
    96. Prashant Pandey*, Shikha Singh*, Michael A. Bender, Jonathan W. Berry, Martín Farach-Colton, Rob Johnson, Thomas M. Kroeger, and Cynthia A. Phillips. "Timely Reporting of Heavy Hitters using External Memory." Proceedings of the International Conference on Management of Data (SIGMOD), pages 1431-1446, June 2020.   *Joint first authors.
    97. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie. "Contention Resolution without Collision Detection." Proceedings of the 52st Annual ACM Symposium on the Theory of Computing (STOC), pages 105-118, June 2020.
    98. Kunal Agrawal, Michael A. Bender, Jeremy Fineman, Seth Gilbert, and Maxwell Young. "Contention Resolution with Message Deadlines." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 23-35, July 2020.
    99. Rathish Das, Kunal Agrawal, Michael A. Bender, Jonathan Berry, Benjamin Moseley, and Cynthia A. Phillips. "How to Manage High-Bandwidth Memory Automatically." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 187-199, July 2020.
    100. Michael A. Bender, Rezaul A. Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Helen Xu. "Closing Gap Between Cache-Oblivious and Cache-Adaptive Analysis." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 63-73, July 2020.
    101. Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. "Brief Announcement: Green Paging and Parallel Paging." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 493-495, July 2020.
    102. Michael A. Bender, Rathish Das, Martín Farach-Colton, Tianchi Mo, David Tench, and Yung Ping Wang. "Mitigating False Positives in Filters: to Adapt or to Cache?" Proceedings of the 2nd Symposium on Algorithmic Principles of Computer System (APoCS), pages 16-24, January 2021.
    103. Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. "Tight Bounds for Parallel Paging and Green Paging." Proceedings of the 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3022-3041, January 2021.
    104. Michael A. Bender and William Kuszmaul. "Randomized Cup Game Algorithms Against Strong Adversaries." Proceedings of the 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2059-2077, January 2021.
    105. Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martín Farach-Colton, Rob Johnson. "Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design." Proceedings of the International Conference on Management of Data (SIGMOD), pages 1386-1399, June 2021.
    106. Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martín Farach-Colton, Rob Johnson, William Kuszmaul, Don Porter, Guido Tagliavini, Janet Vorobyeva, and Evan West. "Paging and the Address Translation Problem." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 105-117, July 2021.
    107. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, and Clifford Stein. "Incremental Edge Orientation in Forests." Proceedings of the 28th Annual European Symposium on Algorithms (ESA), pages 12:1-12:18, September 2021.
    108. Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul. "Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering." Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '21), pages 171-1182, February 2022.
    109. Michael A. Bender, Martín, and William Kuszmaul. "What Does Dynamic Optimality Mean in External Memory?" Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS) Conference, pages 18:1-18:23, January-February 2022.
    110. Yizheng Jiao, Simon Bertron, Sagar Patel, Luke Zeller, Rory Bennett, Nirjhar Mukherjee, Michael A. Bender, Michael Condict, Alex Conway, Martín Farach-Colton, Xiongzi Ge, William Jannen, Rob Johnson, Donald E. Porter, Jun Yuan. "BetrFS: a compleat file system for commodity SSDs." Proceedings of the Seventeenth European Conference on Computer Systems (EuroSys), pages 610-627, April 2022.
    111. David Tench, Evan West, Victor Zhang, Michael A. Bender, Abiyaz Chowdhury, J. Ahmed Dellas, Martín Farach-Colton, Tyler Seip, and Kenny Zhang. "GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams." Proceedings of the International Conference on Management of Data (SIGMOD), pages 325-339, June 2022. https://doi.org/10.1145/3514221.3526146.
    112. Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu. "On the Optimal Time/Space Tradeoff for Hash Tables." Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1284-1297, June 2022. https://doi.org/10.1145/3519935.3519969.
    113. Michael A. Bender, Seth Gilbert, Fabian Kuhn, John Kuszmaul, and Muriel Médard. "Contention Resolution for Coded Radio Networks." Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 119-130, June 2022. https://doi.org/10.1145/3490148.3538573.
    114. Daniel Delayo*, Kenny Zhang*, Kunal Agrawal, Michael A. Bender, Jonathan Berry, Rathish Das, Benjamin Moseley, and Cynthia A. Phillips. "Automatic HBM Management: Models and Algorithms." Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 147-159, June 2022. *Joint first authors. https://doi.org/10.1145/3490148.3538570.
    115. Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. "Online Parallel Paging with Optimal Makespan." Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 205-216, June 2022. Best Paper Finalist. https://doi.org/10.1145/3490148.3538577.
    116. Arghya Bhattacharya, Helen Xu, Abiyaz Chowdhury, Rezaul A. Chowdhury, Rathish Das, Rob Johnson, Rishab Nithyanand, and Michael A. Bender. "When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting." Proceedings of the 30th European Symposium on Algorithms (ESA), pages 16:1-16:17, September 2022. https://doi.org/10.4230/LIPIcs.ESA.2022.16.
    117. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein. "Online List Labeling: Breaking the $\log^2 n$ Barrier." Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 980-990, November 2022. https://doi.org/10.1109/FOCS54457.2022.00096.
    118. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Guido Tagliavini. "Tiny Pointers." Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 477--508, January 2023. https://doi.org/10.1137/1.9781611977554.ch21.
    119. Krishnan Gosakan, Jaehyun Han, William Kuszmaul, Ibrahim Nael Mubarek, Nirjhar Mukherjee, Guido Tagliavini, Evan West, Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martín Farach-Colton, Jayneel Gandhi, Rob Johnson, Sudarsun Kannan, Donald Porter. "Mosaic Pages: Big TLB Reach with Small Pages." Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Volume 3, pages 433-448, March 2023. Distinguished Paper Award. https://doi.org/10.1145/3582016.3582021.
    120. Michael A. Bender, Rathish Das, Martín Farach-Colton, and Guido Tagliavini. "An Associativity Threshold Phenomenon in Set-Associative Caches." Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 117-127, June 2023. https://doi.org/10.1145/3558481.3591084.
    121. Michael A. Bender, Daniel Delayo, Bradley C. Kuszmaul, William Kuszmaul, and Evan West. "Increment-and-Freeze: Every Cache, Everywhere, All of the Time." Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 129-139, June 2023. https://doi.org/10.1145/3558481.3591085.
    122. Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela. "The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems." Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), 3:1-3:19, July 2023. https://doi.org/10.4230/LIPIcs.ECRTS.2023.3.
    123. Michael A. Bender, Martín, Farach-Colton, John Kuszmaul, and William Kuszmaul. "Modern Hashing Made Simple." Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA), pages 363-373, January 2024. https://doi.org/10.1137/1.9781611977936.33.
    124. Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, and Noa Schiller. "History-Independent Concurrent Objects." Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 14-24, June 2024. https://doi.org/10.1145/3662158.3662814.
    125. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, John Kuszmaul, and Maxwell Young. "Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention Resolution." Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 231-242, June 2024. https://doi.org/10.1145/3662158.3662807.
    126. Michael A. Bender, William Kuszmaul, and Renfei Zhou. "Tight Bounds for Classical Open Addressing." Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), November, 2024.
    127. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucky, William Kuszmaul, and Michael Saks. "Nearly Optimal List Labeling." Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), November, 2024.
    128. David Tench, Evan West, Kenny Zhang, Michael A. Bender, Daniel Delayo, Martín Farach-Colton, Gilvir Gill, Tyler Seip, Victor Zhang. "Exploring the Landscape of Distributed Graph Sketching." Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), June 2025. To appear.

    Technical Magazine Articles

    1. Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, and Maxwell Young. "Resource-Competitive Algorithms." SIGACT News, 46(3): 57-71, 2015. [PDF] [postscript]
    2. Michael Bender, Martín, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. "An Introduction to Bε-Trees and Write-Optimization" :login; magazine, 40(5): 22-28, October 2015. [PDF] [postscript]
    3. Alex Conway, Ainesh Bakshi, Yizheng Jiao, Yang Zhan, Michael A. Bender, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Martín Farach-Colton. "How to Fragment Your File System" :login; magazine, 42(2), 2017.
    4. Yang Zhan, Alexander Conway, Yizheng Jiao, Nirjhar Mukherjee, Ian Groombridge, Michael A. Bender, Martín Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, and Jun Yuan. "How to Not Copy Files" :login; magazine, 45(3), 2020.

    Other Selected Talks

    1. Michael A. Bender and Martín Farach-Colton. "I/O and Databases." STOC Tutorial on Algorithms for Memory-Sensitive Computing, 44th ACM Symposium on Theory of Computing (STOC), May 2012. [talk]
    2. Michael A. Bender. "Write-Optimized Data Structures." Dagstuhl Seminar on Database Workload Management, July 2012. [talk]
    3. Michael A. Bender and Bradley C. Kuszmaul. "Data Structures and Algorithms for Big Databases." 6th Extremely Large Databases Conference, Workshop, and Tutorials (XLDB), September 2012. [talk]
    4. Michael A. Bender and Bradley C. Kuszmaul. "Data Structures and Algorithms for Big Databases." 7th Extremely Large Databases Conference, Workshop, and Tutorials (XLDB), September 2013. [talk]
    5. Michael A. Bender and Bradley C. Kuszmaul. "Data Structures and Algorithms for Big Databases." BigData Techcon, October 2014. [talk]
    6. Michael A. Bender. "Keynote talk: TBD." 10th ACM International Workshop on Foundations of Mobile Computing (FOMC), August 2014. [talk]