William Kuszmaul

Inf. Process. Lett., August, 2023

IcebergHT: High Performance Hash Tables Through Stability and Low Associativity.

[BibT_eX]

[DOI]

Proc. ACM Manag. Data, 2023

Increment - and - Freeze: Every Cache, Everywhere, All of the Time.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Tiny Pointers.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Tight Bounds for Monotone Minimal Perfect Hashing.

[BibT_eX]

[DOI]

Sepehr Assadi

Martin Farach-Colton

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Strongly History-Independent Storage Allocation: New Upper and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Mosaic Pages: Big TLB Reach with Small Pages.

[BibT_eX]

[DOI]

Abhishek Bhattacharjee

Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 2023

2022

Train tracks with gaps: Applying the probabilistic method to trains.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity.

[BibT_eX]

[DOI]

CoRR, 2022

A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem.

[BibT_eX]

[DOI]

Nikhil Bansal

John Kuszmaul

CoRR, 2022

On the optimal time/space tradeoff for hash tables.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Online Parallel Paging with Optimal Makespan.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

What Does Dynamic Optimality Mean in External Memory?

[BibT_eX]

[DOI]

Martin Farach-Colton

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game.

[BibT_eX]

[DOI]

Shyam Narayanan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Online List Labeling: Breaking the log<sup>2</sup>n Barrier.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Balanced Allocations: The Heavily Loaded Case with Deletions.

[BibT_eX]

[DOI]

Nikhil Bansal

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.

[BibT_eX]

[DOI]

Zoe Xi

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

All-Purpose Hashing.

[BibT_eX]

[DOI]

CoRR, 2021

Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering.

[BibT_eX]

[DOI]

CoRR, 2021

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis.

[BibT_eX]

[DOI]

Qi Qi

CoRR, 2021

Binary Dynamic Time Warping in Linear Time.

[BibT_eX]

[DOI]

CoRR, 2021

How asymmetry helps buffer management: achieving optimal tail size in cup games.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Paging and the Address-Translation Problem.

[BibT_eX]

[DOI]

Abhishek Bhattacharjee

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Floors and Ceilings in Divide-and-Conquer Recurrences.

[BibT_eX]

[DOI]

Charles E. Leiserson

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Randomized Cup Game Algorithms Against Strong Adversaries.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Tight Bounds for Parallel Paging and Green Paging.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Variable-Processor Cup Game.

[BibT_eX]

[DOI]

Alek Westover

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Train Tracks with Gaps.

[BibT_eX]

[DOI]

Proceedings of the 10th International Conference on Fun with Algorithms, 2021

Stochastic and Worst-Case Generalized Sorting Revisited.

[BibT_eX]

[DOI]

Shyam Narayanan

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Incremental Edge Orientation in Forests.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

The one-way communication complexity of dynamic time warping distance.

[BibT_eX]

[DOI]

J. Comput. Geom., 2020

New results on families of pattern-replacement equivalences.

[BibT_eX]

[DOI]

Ziling Zhou

Discret. Math., 2020

Algorithms and Lower Bounds for the Worker-Task Assignment Problem.

[BibT_eX]

[DOI]

CoRR, 2020

In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory: An In-Place Algorithm With Provably Optimal Cache Behavior.

[BibT_eX]

[DOI]

Alek Westover

CoRR, 2020

Contention resolution without collision detection.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory.

[BibT_eX]

[DOI]

Alek Westover

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis.

[BibT_eX]

[DOI]

Rezaul Alam Chowdhury

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Green Paging and Parallel Paging.

[BibT_eX]

[DOI]

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Flushing Without Cascades.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Cilkmem: Algorithms for Analyzing the Memory High-Water Mark of Fork-Join Parallel Programs.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Algorithmic Principles of Computer Systems, 2020

2019

Achieving optimal backlog in multi-processor cup games.

[BibT_eX]

[DOI]

Martin Farach-Colton

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Efficiently Approximating Edit Distance Between Pseudorandom Strings.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The One-Way Communication Complexity of Dynamic Time Warping Distance.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations.

[BibT_eX]

[DOI]

Math. Comput., 2018

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Signed enumeration of upper-right corners in path shuffles.

[BibT_eX]

[DOI]

Eur. J. Comb., 2017

2016

Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.

[BibT_eX]

[DOI]

CoRR, 2016

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

2014

Brief announcement: few buffers, many hot spots, and no tree saturation (with high probability).

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Avoiding Tree Saturation in the Face of Many Hotspots with Few Buffers.

[BibT_eX]

[DOI]

William H. Kuszmaul

Proceedings of the 2014 IEEE International Conference on High Performance Computing and Communications, 2014

2013

Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns.

[BibT_eX]

[DOI]