William Kuszmaul

I am a 4th-year PhD student in Computer Science at MIT, where I am advised by Charles Leiserson.

My research focuses on randomized algorithms and data structures. Many of my papers use technique from probabilistic combinatorics in order to solve problems in algorithms.

I am funded by the Hertz Fellowship and the NSF GRFP Fellowship. I can be contacted at kuszmaul at mit dot edu.


Link to my Blog: Algorithm Soup.

My CV.


Conference Papers


Note: In theoretical computer science, it is customary to sort the authors of each paper aphabetically.
Papers are presented in reverse chronological order.

  1. William Kuszmaul and Shyam Narayanan. Stochastic and Worst-Case Generalized Sorting Revisited.
    FOCS, 2021. (To appear.)

  2. Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering.
    FOCS, 2021. (To appear.)

  3. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, Clifford Stein. Incremental Edge Orientation in Forests.
    ESA, 2021. (To appear.)

  4. William Kuszmaul. How Asymmetry Helps Load Balancing: Achieving Optimal Tail Size in Multi-Processor Cup Games.
    STOC, 2021.

  5. William Kuszmaul and Charles E. Leiserson. Floors and Ceilings in Divide-and-Conquer Recurrences.
    SOSA, 2021.

  6. Michael A. Bender and William Kuszmaul. Randomized Cup Game Algorithms Against Strong Adversaries.
    SODA ,2021.

  7. Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato. Tight Bounds for Parallel Paging and Green Paging.
    SODA,
    2021.

  8. William Kuszmaul and Alek Westover. The Variable-Processor Cup Game.
    ITCS, 2021.

  9. Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martín Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul et al. Paging and the Address-Translation Problem.
    SPAA,
    2021.

  10. William Kuszmaul. Train Tracks with Gaps.
    10th International Conference on Fun with Algorithms (FUN), 2020.
    Best paper winner.

  11. Michael A Bender, Rezaul A Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis.
    SPAA, 2020.

  12. William Kuszmaul and Alek Westover. Brief Announcement: Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory.
    SPAA, 2020.

  13. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie. Contention Resolution without Collision Detection.
    STOC, 2020.

  14. Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, and William Kuszmaul. Flushing Without Cascades.
    SODA, 2020.

  15. William Kuszmaul. Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game.
    SODA, 2020
    .

  16. Tim Kaler, William Kuszmaul, Tao B. Schardl, and Daniele Vettorel. Cilkmem: Algorithms for Analyzing the Memory High-Water Mark of Fork-Join Parallel Programs.
    APOCS, 2020.
    Best paper finalist.

  17. Michael A. Bender, Martín Farach-Colton, and William Kuszmaul. Achieving Optimal Backlog in Multi-Processor Cup Games.
    STOC, 2019.

  18. Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, and Lin F. Yang. The One-Way Communication Complexity of Dynamic Time Warping Distance.
    SOCG, 2019.

  19. William Kuszmaul. Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation.
    ICALP, 2019.

  20. William Kuszmaul. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
    SODA, 2019.

  21. Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul. On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
    ICALP, 2019.

  22. William Kuszmaul. Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.
    SPAA, 2016.

  23. Hideaki Kimura, William Kuszmaul, and Harumi Kuno. An Embedded Database for Modern Hardware.
    Hewlett Packard Tech Con, 2015.
    (Only 48 out of 1,714 submissions accepted.)

  24. Bradley C. Kuszmaul and William Kuszmaul. Avoiding Tree Saturation in the Face of Many Hotspots with Few Buffers.
    HPCC, 2014.

Papers in Combinatorics and Abstract Algebra


  1. William Kuszmaul and Ziling Zhou. New Results on Families of Pattern-Replacement Equivalences.
    Discrete Mathematics, 2020.

  2. William Kuszmaul. Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations.
    Mathematics of Computation, 2017.
    Software and Data
    Released on Github.

  3. William Kuszmaul. Signed Enumeration of Upper-Right Corners in Path Shuffles.
    European Journal of Combinatorics, 2017.

  4. William Kuszmaul. Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns.
    The Electronic Journal of Combinatorics, 2013.

  5. Surya Bhupatiraju, Pavel Etingof, David Jordan, William Kuszmaul, Jason Li. Lower Central Series of a Free Associative Algebra Over the Integers and Finite Fields.
    Journal of Algebra, 2012.


Unpublished Notes and Papers


  1. William Kuszmaul. Binary Dynamic Time Warping in Linear Time. 2021.

  2. William Kuszmaul and Qi Qi. The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis. 2021.

  3. Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein. Algorithms and Lower Bounds for the Worker-Task Assignment Problem. 2020.

  4. William Kuszmaul. A New Approach to Enumerating Statistics Modulo n. 2013.


Select Awards and Honors

  • Best Paper Award, FUN 2020.

  • Best Paper Finalist, APOCS 2020.

  • 2018 Hertz Fellowship Winner.

  • 2018 NSF Graduate Research Fellowship Winner.

  • 2018 MIT Akamai Fellowship Winner.

  • The 2018 Stanford Kennedy Thesis Prize.
    Awarded to the best honors thesis in the school of engineering.

  • The 2018 Stanford J. E Wallace Sterling Award for Scholastic Achievement.
    Awarded to top 25 students of each year's Stanford graduating class who majored in the humanities or sciences.

  • The 2016-2018 Goldwater Scholarship ($15,000).
    Awarded for paper ``Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations.''

  • Best Poster Award at the 2017 Stanford CURIS Undergraduate Computer Science Poster Session.
    Awarded for poster ``Approximation Algorithms for String Alignment.''

  • 2014 Intel Science Talent Search 3rd Place in Country ($50,000).
    Awarded for paper ``A New Approach to Enumerating Statistics Modulo n.''

  • 2013 Davidson Fellows Scholarship ($10,000), Top 20 Projects in USA.
    Awarded for paper ``Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns.''

  • 2012 Siemens Competition Finalist ($1,000), Top 30 Team Projects in USA.
    Awarded for paper ``Equivalence Classes in $S_n$ for Three Families of Pattern-Replacement Relations.''

  • 2011 Siemens Competition Finalist ($1,000), Top 30 Team Projects in USA.
    Awarded for paper ``Lower Central Series of a Free Associative Algebra Over the Integers and Finite Fields.''


My Blog: Algorithm Soup
(Has now received more than 75,000 views!)