Cover Image

Static Retrieval Revisited: To Optimality and Beyond

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hu, Yang, Kuszmaul, William, Liang, Jingxun, Yu, Huacheng, Zhang, Junkai, Zhou, Renfei
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

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

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 Static Fully Indexable Dictionaries
by: Liang, Jingxun, et al.
Published: (2025)

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

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

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

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
by: Velusamy, Santhoshini, et al.
Published: (2025)

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

Tight Analyses of Ordered and Unordered Linear Probing
by: Braverman, Mark, et al.
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)

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

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

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

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

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)

Adversarial Robustness on Insertion-Deletion Streams
by: Gribelyuk, Elena, et al.
Published: (2026)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
by: Gribelyuk, Elena, et al.
Published: (2024)

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

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
by: Gribelyuk, Elena, et al.
Published: (2024)

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

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Revisiting Local Computation of PageRank: Simple and Optimal
by: Wang, Hanzhi, et al.
Published: (2024)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
by: Wang, Hanzhi
Published: (2024)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Optimal Communication for Classic Functions in the Coordinator Model and Beyond
by: Esfandiari, Hossein, et al.
Published: (2024)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)