William Kuszmaul

121 papers A* 36A 4B 12Misc 1Journal 62Unranked 5
YearRankTypeTitle / Venue / Authors
2026 A* conf
History-Independent Load Balancing.
SODA
Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver
2026 J jnl
History-Independent Load Balancing.
CoRR
Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver
2026 A* conf
History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees.
SODA
Rathish Das, William Kuszmaul
2026 A* conf
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck.
SODA
William Kuszmaul, Jingxun Liang, Renfei Zhou
2025 — conf
A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations.
SOSA
William Kuszmaul
2025 J jnl
A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations.
CoRR
William Kuszmaul
2025 B conf
Don't Melt Your Cache: Low-Associativity with Heat-Sink.
SPAA
Michael A. Bender, Alex Conway, Daniel DeLayo, Martin Farach-Colton, Jaehyun Han, Linfeng He, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Donald E. Porter, Evan West
2025 A* conf
Efficient
SODA
William Kuszmaul, Michael Mitzenmacher
2025 J jnl
Efficient
CoRR
William Kuszmaul, Michael Mitzenmacher
2025 A* conf
Fingerprint Filters Are Optimal.
FOCS
William Kuszmaul, Jingxun Liang, Renfei Zhou
2025 J jnl
Fingerprint Filters Are Optimal.
CoRR
William Kuszmaul, Jingxun Liang, Renfei Zhou
2025 J jnl
Online List Labeling: Breaking the \({\log^2 n}\) Barrier.
SIAM J. Comput.
Michael A. Bender, Alexander Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein
2025 J jnl
Optimal Bounds for Open Addressing Without Reordering.
CoRR
Martin Farach-Colton, Andrew Krapivin, William Kuszmaul
2025 J jnl
Optimal Non-Oblivious Open Addressing.
CoRR
Michael A. Bender, William Kuszmaul, Renfei Zhou
2025 A* conf
Optimal Non-oblivious Open Addressing.
STOC
Michael A. Bender, William Kuszmaul, Renfei Zhou
2025 J jnl
Paging and the Address-Translation Problem.
ACM Trans. Algorithms
Michael A. Bender, Abhishek Bhattacharjee, Alexander Conway, Martin Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Nirjhar Mukherjee, Donald E. Porter, Guido Tagliavini, Janet Vorobyeva, Evan West
2025 A* conf
Static Retrieval Revisited: To Optimality and Beyond.
FOCS
Yang Hu, William Kuszmaul, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou
2025 J jnl
Static Retrieval Revisited: To Optimality and Beyond.
CoRR
Yang Hu, William Kuszmaul, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou
2025 J jnl
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck.
CoRR
William Kuszmaul, Jingxun Liang, Renfei Zhou
2025 J jnl
Tight Analyses of Ordered and Unordered Linear Probing.
CoRR
Mark Braverman, William Kuszmaul
2025 A* conf
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval.
SODA
William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou
2025 J jnl
Tight Bounds for Monotone Minimal Perfect Hashing.
ACM Trans. Algorithms
Sepehr Assadi, Martín Farach-Colton, William Kuszmaul
2025 J jnl
Tiny Pointers.
ACM Trans. Algorithms
Michael A. Bender, Alexander Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini
2024 B conf
A Nearly Quadratic Improvement for Memory Reallocation.
SPAA
Martin Farach-Colton, William Kuszmaul, Nathan S. Sheffield, Alek Westover
2024 J jnl
A Nearly Quadratic Improvement for Memory Reallocation.
CoRR
Martin Farach-Colton, William Kuszmaul, Nathan S. Sheffield, Alek Westover
2024 B conf
Distributed Load Balancing in the Face of Reappearance Dependencies.
SPAA
Kunal Agrawal, William Kuszmaul, Zhe Wang, Jinhao Zhao
2024 J jnl
Layered List Labeling.
CoRR
Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul
2024 J jnl
Layered List Labeling.
Proc. ACM Manag. Data
Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul
2024 — conf
Modern Hashing Made Simple.
SOSA
Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul
2024 J jnl
Mosaic Pages: Big TLB Reach With Small Pages.
IEEE Micro
Jaehyun Han, Krishnan Gosakan, 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
2024 A* conf
Nearly Optimal List Labeling.
FOCS
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks
2024 J jnl
Nearly Optimal List Labeling.
CoRR
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks
2024 A* conf
Optimal Bounds for Open Addressing Without Reordering.
FOCS
Martín Farach-Colton, Andrew Krapivin, William Kuszmaul
2024 B conf
Scheduling Jobs with Work-Inefficient Parallel Solutions.
SPAA
William Kuszmaul, Alek Westover
2024 J jnl
Scheduling Jobs with Work-Inefficient Parallel Solutions.
CoRR
William Kuszmaul, Alek Westover
2024 A* conf
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval.
STOC
William Kuszmaul, Stefan Walzer
2024 A* conf
Tight Analyses of Ordered and Unordered Linear Probing.
FOCS
Mark Braverman, William Kuszmaul
2024 J jnl
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval.
CoRR
William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou
2024 A* conf
Tight Bounds for Classical Open Addressing.
FOCS
Michael A. Bender, William Kuszmaul, Renfei Zhou
2024 J jnl
Tight Bounds for Classical Open Addressing.
CoRR
Michael A. Bender, William Kuszmaul, Renfei Zhou
2024 A* conf
Towards an Analysis of Quadratic Probing.
ICALP
William Kuszmaul, Zoe Xi
2023 J jnl
A nearly tight lower bound for the
Inf. Process. Lett.
Nikhil Bansal, John Kuszmaul, William Kuszmaul
2023 J jnl
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once.
J. ACM
Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini
2023 J jnl
IcebergHT: High Performance Hash Tables Through Stability and Low Associativity.
Proc. ACM Manag. Data
Prashant Pandey, Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini, Rob Johnson
2023 B conf
Increment - and - Freeze: Every Cache, Everywhere, All of the Time.
SPAA
Michael A. Bender, Daniel DeLayo, Bradley C. Kuszmaul, William Kuszmaul, Evan West
2023 — conf
Mosaic Pages: Big TLB Reach with Small Pages.
ASPLOS (3)
Krishnan Gosakan, Jaehyun Han, William Kuszmaul, Ibrahim N. Mubarek, Nirjhar Mukherjee, Karthik Sriram, Guido Tagliavini, Evan West, Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Jayneel Gandhi, Rob Johnson, Sudarsun Kannan, Donald E. Porter
2023 — —
Randomized Data Structures: New Perspectives and Hidden Surprises
William Kuszmaul
2023 A* conf
Strongly History-Independent Storage Allocation: New Upper and Lower Bounds.
FOCS
William Kuszmaul
2023 A* conf
Tight Bounds for Monotone Minimal Perfect Hashing.
SODA
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
2023 A* conf
Tiny Pointers.
SODA
Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini
2022 A* conf
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits.
FOCS
William Kuszmaul
2022 J jnl
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits.
CoRR
William Kuszmaul
2022 J jnl
A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem.
CoRR
Nikhil Bansal, John Kuszmaul, William Kuszmaul
2022 A conf
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
ESA
Zoe Xi, William Kuszmaul
2022 J jnl
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
CoRR
Zoe Xi, William Kuszmaul
2022 A* conf
Balanced Allocations: The Heavily Loaded Case with Deletions.
FOCS
Nikhil Bansal, William Kuszmaul
2022 J jnl
Balanced Allocations: The Heavily Loaded Case with Deletions.
CoRR
Nikhil Bansal, William Kuszmaul
2022 J jnl
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity.
CoRR
Prashant Pandey, Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini, Rob Johnson
2022 A* conf
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost.
ICALP
Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein
2022 A* conf
On the optimal time/space tradeoff for hash tables.
STOC
Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu
2022 A* conf
Online List Labeling: Breaking the log
FOCS
Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein
2022 J jnl
Online List Labeling: Breaking the log
CoRR
Michael A. Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein
2022 B conf
Online Parallel Paging with Optimal Makespan.
SPAA
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato
2022 A* conf
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game.
ICALP
William Kuszmaul, Shyam Narayanan
2022 J jnl
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game.
CoRR
William Kuszmaul, Shyam Narayanan
2022 J jnl
Tight Bounds for Monotone Minimal Perfect Hashing.
CoRR
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
2022 J jnl
Train tracks with gaps: Applying the probabilistic method to trains.
Theor. Comput. Sci.
William Kuszmaul
2022 A conf
What Does Dynamic Optimality Mean in External Memory?
ITCS
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
2022 J jnl
What Does Dynamic Optimality Mean in External Memory?
CoRR
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
2021 J jnl
All-Purpose Hashing.
CoRR
Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini
2021 J jnl
Binary Dynamic Time Warping in Linear Time.
CoRR
William Kuszmaul
2021 — conf
Floors and Ceilings in Divide-and-Conquer Recurrences.
SOSA
William Kuszmaul, Charles E. Leiserson
2021 J jnl
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games.
CoRR
William Kuszmaul
2021 A* conf
How asymmetry helps buffer management: achieving optimal tail size in cup games.
STOC
William Kuszmaul
2021 A conf
Incremental Edge Orientation in Forests.
ESA
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, Clifford Stein
2021 J jnl
Incremental Edge Orientation in Forests.
CoRR
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, Clifford Stein
2021 J jnl
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering.
CoRR
Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul
2021 A* conf
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering.
FOCS
Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul
2021 J jnl
On the Optimal Time/Space Tradeoff for Hash Tables.
CoRR
Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu
2021 B conf
Paging and the Address-Translation Problem.
SPAA
Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Nirjhar Mukherjee, Donald E. Porter, Guido Tagliavini, Janet Vorobyeva, Evan West
2021 A* conf
Randomized Cup Game Algorithms Against Strong Adversaries.
SODA
Michael A. Bender, William Kuszmaul
2021 A* conf
Stochastic and Worst-Case Generalized Sorting Revisited.
FOCS
William Kuszmaul, Shyam Narayanan
2021 J jnl
Stochastic and Worst-Case Generalized Sorting Revisited.
CoRR
William Kuszmaul, Shyam Narayanan
2021 J jnl
The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis.
CoRR
William Kuszmaul, Qi Qi
2021 A conf
The Variable-Processor Cup Game.
ITCS
William Kuszmaul, Alek Westover
2021 A* conf
Tight Bounds for Parallel Paging and Green Paging.
SODA
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato
2021 J jnl
Tiny Pointers.
CoRR
Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini
2021 Misc conf
Train Tracks with Gaps.
FUN
William Kuszmaul
2020 A* conf
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game.
SODA
William Kuszmaul
2020 J jnl
Algorithms and Lower Bounds for the Worker-Task Assignment Problem.
CoRR
Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein
2020 B conf
Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory.
SPAA
William Kuszmaul, Alek Westover
2020 — conf
Cilkmem: Algorithms for Analyzing the Memory High-Water Mark of Fork-Join Parallel Programs.
APOCS
Tim Kaler, William Kuszmaul, Tao B. Schardl, Daniele Vettorel
2020 B conf
Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis.
SPAA
Michael A. Bender, Rezaul Alam Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Helen Xu
2020 J jnl
Contention Resolution Without Collision Detection.
CoRR
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
2020 A* conf
Contention resolution without collision detection.
STOC
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
2020 A* conf
Flushing Without Cascades.
SODA
Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul
2020 B conf
Green Paging and Parallel Paging.
SPAA
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato
2020 J jnl
In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory: An In-Place Algorithm With Provably Optimal Cache Behavior.
CoRR
William Kuszmaul, Alek Westover
2020 J jnl
New results on families of pattern-replacement equivalences.
Discret. Math.
William Kuszmaul, Ziling Zhou
2020 J jnl
The Variable-Processor Cup Game.
CoRR
William Kuszmaul, Alek Westover
2020 J jnl
The one-way communication complexity of dynamic time warping distance.
J. Comput. Geom.
Vladimir Braverman, Moses Charikar, William Kuszmaul, Lin F. Yang
2020 J jnl
Train Tracks with Gaps: Applying the Probabilistic Method to Trains.
CoRR
William Kuszmaul
2019 J jnl
Achieving Optimal Backlog in Multi-Processor Cup Games.
CoRR
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
2019 J jnl
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game.
CoRR
William Kuszmaul
2019 A* conf
Achieving optimal backlog in multi-processor cup games.
STOC
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
2019 J jnl
Cilkmem: Algorithms for Analyzing the Memory High-Water Mark of Fork-Join Parallel Programs.
CoRR
Tim Kaler, William Kuszmaul, Tao B. Schardl, Daniele Vettorel
2019 A* conf
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation.
ICALP
William Kuszmaul
2019 J jnl
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation.
CoRR
William Kuszmaul
2019 A* conf
Efficiently Approximating Edit Distance Between Pseudorandom Strings.
SODA
William Kuszmaul
2019 A* conf
The One-Way Communication Complexity of Dynamic Time Warping Distance.
SoCG
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2019 J jnl
The One-Way Communication Complexity of Dynamic Time Warping Distance.
CoRR
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2018 J jnl
Efficiently Approximating Edit Distance Between Pseudorandom Strings.
CoRR
William Kuszmaul
2018 J jnl
Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations.
Math. Comput.
William Kuszmaul
2018 A* conf
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
ICALP
Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul
2018 J jnl
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
CoRR
Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul
2017 J jnl
Signed enumeration of upper-right corners in path shuffles.
Eur. J. Comb.
William Kuszmaul
2016 B conf
Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.
SPAA
William Kuszmaul
2016 J jnl
Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.
CoRR
William Kuszmaul
2015 J jnl
Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations.
CoRR
William Kuszmaul
2014 B conf
Brief announcement: few buffers, many hot spots, and no tree saturation (with high probability).
SPAA
Bradley C. Kuszmaul, William Kuszmaul
2013 J jnl
Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns.
Electron. J. Comb.
William Kuszmaul