Buchumschlag

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kuszmaul, William, Putterman, Aaron, Xu, Tingqiang, Zhou, Hangrui, Zhou, Renfei
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Tight Bounds for Classical Open Addressing
von: Bender, Michael A., et al.
Veröffentlicht: (2024)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
von: Kuszmaul, William, et al.
Veröffentlicht: (2025)

Fingerprint Filters Are Optimal
von: Kuszmaul, William, et al.
Veröffentlicht: (2025)

Optimal Non-Oblivious Open Addressing
von: Bender, Michael A., et al.
Veröffentlicht: (2025)

Static Retrieval Revisited: To Optimality and Beyond
von: Hu, Yang, et al.
Veröffentlicht: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Tight Analyses of Ordered and Unordered Linear Probing
von: Braverman, Mark, et al.
Veröffentlicht: (2025)

Tight Bounds for Sparsifying Random CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
von: Kuszmaul, William
Veröffentlicht: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Optimal Bounds for Open Addressing Without Reordering
von: Farach-Colton, Martin, et al.
Veröffentlicht: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
von: Kuszmaul, William, et al.
Veröffentlicht: (2024)

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

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Optimal Static Fully Indexable Dictionaries
von: Liang, Jingxun, et al.
Veröffentlicht: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

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

Tight Sampling Bounds for Eigenvalue Approximation
von: Swartworth, William, et al.
Veröffentlicht: (2024)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

On the Parallel Complexity of Finding a Matroid Basis
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Tight Bounds for Sampling q-Colorings via Coupling from the Past
von: Ding, Tianxing, et al.
Veröffentlicht: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
von: Dadush, Daniel, et al.
Veröffentlicht: (2025)

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

Nearly Optimal Internal Dictionary Matching
von: Chen, Jingbang, et al.
Veröffentlicht: (2023)

A Nearly Quadratic Improvement for Memory Reallocation
von: Farach-Colton, Martin, et al.
Veröffentlicht: (2024)

History-Independent Load Balancing
von: Bender, Michael A., et al.
Veröffentlicht: (2026)

Almost Tight Bounds for Online Hypergraph Matching
von: Tröbst, Thorben, et al.
Veröffentlicht: (2024)

Tight Bounds for Sorting Under Partial Information
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2024)

Nearly Tight Bounds for the Online Sorting Problem
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
von: Kosolobov, Dmitry
Veröffentlicht: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
von: Dinitz, Michael, et al.
Veröffentlicht: (2023)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Many Hamiltonians Are Sparsifiable
von: Basu, Arpon, et al.
Veröffentlicht: (2026)

Optimal Static Dictionary with Worst-Case Constant Query Time
von: Hu, Yang, et al.
Veröffentlicht: (2024)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)