WK
William Kuszmaul
cs.DSmath.COcs.DCcs.DMcs.DBcs.LGmath.PRmath.QAmath.RA
On Valency
published · living versionsW_8frnrrj6·v1 · currentpublished
Catalan Hashing: Efficient Linear Probing for Variable-Length Items
with Alex Conway, Hanna Komlós
1 version
Preprints & journals
66 papers in the corpus · 2012–2026With Leverage, the Gambler is Not the One Who Gets Ruined2610.19239v1 · William Kuszmaul2026 · 0 citationsarXiv
The Power of Two-Choice Linear Probing2610.00688v1 · Amir Azarmehr, Michael A. Bender, William Kuszmaul et al.2026 · 0 citationsFOCS 2026
Tight Bounds for Memory Allocation With and Without Request Fragmentation2608.28462v1 · Michael A. Bender, Alex Conway, Mart'in Farach-Colton et al.2026 · 0 citationsarXiv
Quadratic Probing Insertions Are Time2608.28512v2 · Yang Hu, William Kuszmaul, Jingxun Liang et al.2026 · 0 citationsarXiv
Lower Bounds for Linear Hashing via Arithmetic Kakeya2608.24866v2 · Ainesh Bakshi, Alex Conway, Hanna Koml'os et al.2026 · 0 citationsarXiv
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space2608.06066v1 · Guy E. Blelloch, Yang Hu, William Kuszmaul et al.2026 · 0 citationsarXiv
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries2608.06077v1 · Guy E. Blelloch, Yang Hu, William Kuszmaul et al.2026 · 0 citationsarXiv
An Analysis of Brent's Insertion Method for Hash Tables2608.00762v1 · William Kuszmaul2026 · 0 citationsarXiv
Succinct and Fast Tiny Pointer Hash Tables2607.28892v1 · Xilin Tang, Yuqi Mai, William Kuszmaul et al.2026 · 0 citationsProc. VLDB Endow. 19(9) (2026) 2168-2182
Fast Insertion for Bucketized Cuckoo Hashing2607.24545v1 · Tolson Bell, William Kuszmaul2026 · 0 citationsarXiv
Dynamic and Optimal Function Inversion in the Small-Time Regime2609.20240v1 · John Kuszmaul, William Kuszmaul2026 · 0 citationsarXiv
Linear Probing with Non-Greedy Insertions2607.17494v2 · Andrew Krapivin, William Kuszmaul, Yixuan Wang2026 · 0 citationsarXiv
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood2607.13247v1 · Yang Hu, William Kuszmaul, Jingxun Liang et al.2026 · 0 citationsarXiv
Resizable Retrieval2606.15944v1 · William Kuszmaul, Aaron Putterman, Tingqiang Xu et al.2026 · 0 citationsarXiv
History-Independent Load Balancing2602.11953v1 · Michael A. Bender, William Kuszmaul, Elaine Shi et al.2026 · 0 citationsarXiv
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck2510.19175v1 · William Kuszmaul, Jingxun Liang, Renfei Zhou2025 · 1 citationarXiv
Static Retrieval Revisited: To Optimality and Beyond2510.18237v1 · Yang Hu, William Kuszmaul, Jingxun Liang et al.2025 · 0 citationsarXiv
Fingerprint Filters Are Optimal2510.18129v1 · William Kuszmaul, Jingxun Liang, Renfei Zhou2025 · 0 citationsarXiv
Optimal Non-Oblivious Open Addressing2503.13628v1 · Michael A. Bender, William Kuszmaul, Renfei Zhou2025 · 2 citationsarXiv
Tight Analyses of Ordered and Unordered Linear Probing2501.11582v1 · Mark Braverman, William Kuszmaul2025 · 1 citationarXiv
A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations2501.03488v3 · William Kuszmaul2025 · 0 citationsarXiv
Optimal Bounds for Open Addressing Without Reordering2501.02305v2 · Martin Farach-Colton, Andrew Krapivin, William Kuszmaul2025 · 3 citationsarXiv
Efficient -ary Cuckoo Hashing at High Load Factors by Bubbling Up2501.02312v1 · William Kuszmaul, Michael Mitzenmacher2025 · 2 citationsarXiv
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval2410.10002v2 · William Kuszmaul, Aaron Putterman, Tingqiang Xu et al.2024 · 1 citationarXiv
Tight Bounds for Classical Open Addressing2409.11280v1 · Michael A. Bender, William Kuszmaul, Renfei Zhou2024 · 2 citationsarXiv
Scheduling Jobs with Work-Inefficient Parallel Solutions2405.11986v1 · William Kuszmaul, Alek Westover2024 · 0 citationsarXiv
A Nearly Quadratic Improvement for Memory Reallocation2405.12152v1 · Martin Farach-Colton, William Kuszmaul, Nathan Sheffield et al.2024 · 1 citationarXiv
Nearly Optimal List Labeling2405.00807v1 · Michael A. Bender, Alex Conway, Mart'in Farach-Colton et al.2024 · 1 citationarXiv
Layered List Labeling2404.16623v1 · Michael A. Bender, Alex Conway, Martin Farach-Colton et al.2024 · 0 citationsarXiv
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity2210.04068v2 · Prashant Pandey, Michael A. Bender, Alex Conway et al.2022 · 3 citationsarXiv
A Nearly Tight Lower Bound for the -Dimensional Cow-Path Problem2209.08427v1 · Nikhil Bansal, John Kuszmaul, William Kuszmaul2022 · 0 citationsarXiv
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits2209.06038v2 · William Kuszmaul2022 · 7 citationsarXiv
Tight Bounds for Monotone Minimal Perfect Hashing2207.10556v2 · Sepehr Assadi, Martin Farach-Colton, William Kuszmaul2022 · 3 citationsarXiv
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings2207.00915v1 · Zoe Xi, William Kuszmaul2022 · 1 citationarXiv
Balanced Allocations: The Heavily Loaded Case with Deletions2205.06558v1 · Nikhil Bansal, William Kuszmaul2022 · 6 citationsarXiv
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game2205.01722v2 · William Kuszmaul, Shyam Narayanan2022 · 2 citationsarXiv
Online List Labeling: Breaking the Barrier2203.02763v3 · Michael A. Bender, Alex Conway, Mart'in Farach-Colton et al.2022 · 0 citationsarXiv
What Does Dynamic Optimality Mean in External Memory?2201.01742v2 · Michael A. Bender, Mart'in Farach-Colton, William Kuszmaul2022 · 0 citationsarXiv
Tiny Pointers2111.12800v1 · Michael A. Bender, Alex Conway, Mart'in Farach-Colton et al.2021 · 0 citationsarXiv
Stochastic and Worst-Case Generalized Sorting Revisited2111.07222v1 · William Kuszmaul, Shyam Narayanan2021 · 3 citationsFOCS 2021
On the Optimal Time/Space Tradeoff for Hash Tables2111.00602v2 · Michael A. Bender, Mart'in Farach-Colton, John Kuszmaul et al.2021 · 22 citationsarXiv
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once2109.04548v3 · Michael A. Bender, Alex Conway, Mart'in Farach-Colton et al.2021 · 25 citationsarXiv
Incremental Edge Orientation in Forests2107.02318v1 · Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul et al.2021 · 2 citationsarXiv
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games2104.05172v1 · William Kuszmaul2021 · 6 citationsarXiv
The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis2102.05077v2 · William Kuszmaul, Qi Qi2021 · 3 citationsarXiv
Binary Dynamic Time Warping in Linear Time2101.01108v2 · William Kuszmaul2021 · 3 citationsarXiv
Train Tracks with Gaps: Applying the Probabilistic Method to Trains2012.00589v1 · William Kuszmaul2020 · 0 citationsFun With Algorithms, 2020
The Variable-Processor Cup Game2012.00127v2 · William Kuszmaul, Alek Westover2020 · 1 citationarXiv
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost2008.10709v2 · Aaron Berger, William Kuszmaul, Adam Polak et al.2020 · 4 citationsarXiv
In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory2004.12532v2 · William Kuszmaul, Alek Westover2020 · 0 citationsarXiv
Career total: 113 works. 66 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.