Monteverde Cloud Forest, Costa Rica
 

Michael A. Bender

Associate Professor

Department of Computer Science
State University of New York at Stony Brook
Stony Brook, NY 11794-4400 
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, FranceDiplô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.

  • Teaching


    Past Teaching


    Awards

    1. Major Contributions to Graduate Education and Research, CS Dept, Stony Brook, 2012.
    2. Imre Simon Test-of-Time Award, 2012.
    3. Undergraduate Teaching Award, Dept of Computer Science, Stony Brook University, 2006.
    4. 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).
    5. PODS Best Newcomer Award, 2006.
    6. Dean's Award for Excellence in Graduate Teaching by a Faculty Member, SUNY Stony Brook, 2005.
    7. Graduate Teaching Award, Dept of Computer Science, SUNY Stony Brook, 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.


    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.


    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]


    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.
    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.
      Winner: 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]
    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), 2014. To appear. [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), 2014 To appear. [PDF] [postscript]

    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]