Cover Image

Tight Analyses of Ordered and Unordered Linear Probing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Braverman, Mark, Kuszmaul, William
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
by: Kuszmaul, William, et al.
Published: (2024)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
by: Kuszmaul, William, et al.
Published: (2024)

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
by: Kuszmaul, William, et al.
Published: (2021)

Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up
by: Kuszmaul, William, et al.
Published: (2025)

Fingerprint Filters Are Optimal
by: Kuszmaul, William, et al.
Published: (2025)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms
by: Xu, Pan
Published: (2024)

Composition Orderings for Linear Functions and Matrix Multiplication Orderings
by: Kubo, Susumu, et al.
Published: (2024)

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Layered List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
by: Braverman, Mark, et al.
Published: (2024)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
by: Feng, Shiyuan, et al.
Published: (2025)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Tight simulation of a distribution using conditional samples
by: Adar, Tomer
Published: (2025)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Tight bounds for the sensitivity of CDAWGs with left-end edits
by: Fujimaru, Hiroto, et al.
Published: (2023)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Computational Complexity of the Interval Ordering Problem
by: Pawlowski, Simeon, et al.
Published: (2026)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)