William Kuszmaul

I am an Assistant Professor of Computer Science at Carnegie Mellon University. My research focuses on the design and analysis of randomized data structures.

I also write a blog named Algorithm Soup.

I can be reached at [last-name]@cmu.edu.

You can also see my slightly out-of-date CV here.

News:

Our paper on distributed load balancing won Best Paper at SPAA'24.
My PhD Thesis won Honorable Mention for the ACM Doctoral Dissertation Award.
My PhD Thesis won the EATCS Distinguished Dissertation Award.
My PhD Thesis won the MIT George M. Sprowls PhD Thesis Award.
Our paper on was selected as an IEEE MICRO Top Pick for 2023.
Quanta Magazine wrote an article on my research.
Our paper on applying data-structural techniques to hardware TLBs won the Distinguished Paper Award at ASPLOS'23.

Publications

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

Aaron L. Putterman, William Kuszmaul, Tingqiang Xu, Hangrui Zhou, Renfei Zhou. Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval.
SODA 2025.
William Kuszmaul and Michael Mitzenmacher. Efficient d-Ary Cuckoo Hashing at High Load Factors by Bubbling Up.
SODA 2025.
William Kuszmaul. A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations.
SOSA 2025.
Talk slides and source code.
Martín Farach-Colton, Andrew Krapivin, William Kuszmaul. Optimal Bounds for Open Addressing Without Reordering.
FOCS 2024.
Mark Braverman and William Kuszmaul. Tight Analyses of Ordered and Unordered Linear Probing.
FOCS 2024.
Michael A. Bender, William Kuszmaul, Renfei Zhou. Tight Bounds for Classical Open Addressing.
FOCS 2024.
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucky, William Kuszmaul, Michael Saks. Nearly Optimal List Labeling.
FOCS 2024.
William Kuszmaul and Zoe Xi. Towards an Analysis of Quadratic Probing.
ICALP, 2024.
William Kuszmaul and Stefan Walzer. Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval.
STOC, 2024.
William Kuszmaul and Alek Westover. Scheduling Jobs with Work-Inefficient Parallel Solutions.
SPAA, 2024.
Martín Farach Colton, William Kuszmaul, Nathan S. Scheffield, and Alek Westover. A Nearly Quadratic Improvement for Memory Reallocation.
SPAA, 2024.
Kunal Agrawal, William Kuszmaul, Zhe Wang, and Jinhao Zhao. Distributed Load Balancing in the Face of Reappearance Dependencies.
SPAA, 2024.
Winner of Best-Paper Award.
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, and William Kuszmaul. Layered List Labeling.
PODS, 2024.
Michael A. Bender, Martín Farach-Colton, John Kuszmaul, and William Kuszmaul. Modern Hashing Made Simple.
SOSA, 2024.
Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini. Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once.
JACM, 2023.
William Kuszmaul. Strongly History Independent Storage Allocation: New Upper and Lower Bounds.
FOCS, 2023.
Nikhil Bansal, John Kuszmaul, William Kuszmaul. A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem.
IPL, 2023.
Michael A. Bender, Daniel DeLayo, Bradley C. Kuszmaul, William Kuszmaul, Evan West. Increment-and-Freeze: Every Cache, Everywhere, All of the Time.
SPAA, 2023.
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, Sudarsun Kannan, Donald E. Porter. Mosaic Pages: Big TLB Reach with Small Pages.
ASPLOS, 2023.
Winner of Distinguished Paper Award.
Selected as IEEE MICRO Top Pick.
Sepehr Assadi, Martín Farach-Colton, William Kuszmaul. Tight Bounds for Monotone Minimal Perfect Hashing.
SODA, 2023.
Invited to Special Issue of TALG.
Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini. Tiny Pointers.
SODA, 2023.
Invited to Special Issue of TALG.
Prashant Pandey, Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini, Rob Johnson. IcebergHT: High-Performance PMEM Hash Tables Through Stability and Low Associativity.
SIGMOD, 2023.
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein. Online List Labeling: Breaking the $\log^2 n$ Barrier.
FOCS, 2022.
Invited to Special Issue of SIGCOMP.
See Nicole Wein's excellent TCS+ Talk.
William Kuszmaul. A Hash Table Without Hash Functions, and How to Get the Most out of Your Random Bits.
FOCS, 2022.
Invited as a Special Presentation at Highlights of Algorithms (HALG) 2023.
Nikhil Bansal and William Kuszmaul. Balanced Allocations: The Heavily Loaded Case with Deletions.
FOCS, 2022.
William Kuszmaul and Zoe Xi. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
ESA, 2022.
Winner of Best Student Paper Award.
Invited as a Highlight Presentation at CPM '23.
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato. Parallel Paging with Optimal Makespan.
SPAA, 2022.
Winner of Best Paper Finalist Award.
William Kuszmaul and Shyam Narayanan. Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game.
ICALP, 2022. (Link to Talk)
Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein. Algorithms and Lower Bounds for the Worker-Task Assignment Problem.
ICALP, 2022. (Appeared as Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost)
Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu. On the Optimal Time/Space Tradeoff for Hash Tables.
STOC, 2022. (Link to Talk)
Featured in Quanta Magazine.
Michael A. Bender, Martín Farach-Colton, William Kuszmaul. What Does Dynamic Optimality Mean in External Memory?
ITCS, 2021. (Link to Talk)
William Kuszmaul and Shyam Narayanan. Stochastic and Worst-Case Generalized Sorting Revisited.
FOCS, 2021. (Link to Talk)
Invited as a Special Presentation at Highlights of Algorithms (HALG) 2022.
Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering.
FOCS, 2021. (Link to Talk )
Covered in MIT Press.
Also given as a TCS+ Talk.
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, Clifford Stein. Incremental Edge Orientation in Forests.
ESA, 2021.
William Kuszmaul. How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Multi-Processor Cup Games.
STOC, 2021.
William Kuszmaul and Charles E. Leiserson. Floors and Ceilings in Divide-and-Conquer Recurrences.
SOSA, 2021.
Michael A. Bender and William Kuszmaul. Randomized Cup Game Algorithms Against Strong Adversaries.
SODA, 2021.
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato. Tight Bounds for Parallel Paging and Green Paging.
SODA, 2021.
William Kuszmaul and Alek Westover. The Variable-Processor Cup Game.
ITCS, 2021.
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, Sudarsun Kannan, Donald E. Porter. Paging and the Address-Translation Problem.
SPAA, 2021.
William Kuszmaul. Train Tracks with Gaps.
10th International Conference on Fun with Algorithms (FUN), 2020.
Winner of Best Paper Award.
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. (Link to Talk)
William Kuszmaul and Alek Westover. Brief Announcement: Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory.
SPAA, 2020.
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie. Contention Resolution without Collision Detection.
STOC, 2020.
Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul. Flushing Without Cascades.
SODA, 2020.
William Kuszmaul. Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game.
SODA, 2020.
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.
Winner of Best Paper Finalist Award.
William Kuszmaul and Ziling Zhou. New Results on Families of Pattern-Replacement Equivalences.
Discrete Mathematics, 2020.
Michael A. Bender, Martín Farach-Colton, William Kuszmaul. Achieving Optimal Backlog in Multi-Processor Cup Games.
STOC, 2019.
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang. The One-Way Communication Complexity of Dynamic Time Warping Distance.
SOCG, 2019.
William Kuszmaul. Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation.
ICALP, 2019.
William Kuszmaul. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
SODA, 2019.
Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul. On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
ICALP, 2018.
William Kuszmaul. Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations.
Mathematics of Computation, 2017.
Software and Data Released on Github.
William Kuszmaul. Signed Enumeration of Upper-Right Corners in Path Shuffles.
European Journal of Combinatorics, 2017.
William Kuszmaul. Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.
SPAA, 2016.
Bradley C. Kuszmaul and William Kuszmaul. Avoiding Tree Saturation in the Face of Many Hotspots with Few Buffers.
HPCC, 2014.
William Kuszmaul. Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns.
The Electronic Journal of Combinatorics, 2013.
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

William Kuszmaul. Binary Dynamic Time Warping in Linear Time. 2021.
William Kuszmaul and Qi Qi. The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis. 2021.
William Kuszmaul. A New Approach to Enumerating Statistics Modulo n. 2013.

Select Awards and Honors

My PhD Thesis won Honorable Mention for the ACM Doctoral Dissertation Award.
My PhD Thesis won the EATCS Distinguished Dissertation Award.
My PhD Thesis won the MIT George M. Sprowls PhD Thesis Award.
IEEE MICRO Top Pick for 2023.
Best Paper, SPAA 2024.
Distinguished Paper, ASPLOS 2023.
Best Student Paper, ESA 2022.
Best Paper Finalist, SPAA 2022.
Best Paper, 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 150,000 views!)