Imagen de Portada

Optimal Static Dictionary with Worst-Case Constant Query Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Hu, Yang, Liang, Jingxun, Yu, Huacheng, Zhang, Junkai, Zhou, Renfei
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Optimal Static Fully Indexable Dictionaries
por: Liang, Jingxun, et al.
Publicado: (2025)

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

Fingerprint Filters Are Optimal
por: Kuszmaul, William, et al.
Publicado: (2025)

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

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

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

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Querying in Constant Expected Time with Learned Indexes
por: Croquevielle, Luis, et al.
Publicado: (2024)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
por: Navarro, Gonzalo
Publicado: (2024)

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

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

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
por: Mao, Xiao
Publicado: (2023)

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

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
por: Bansal, Nikhil, et al.
Publicado: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
por: Grilnberger, Mara, et al.
Publicado: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
por: Abboud, Amir, et al.
Publicado: (2024)

Beyond Worst Case Local Computation Algorithms
por: Biswas, Amartya Shankha, et al.
Publicado: (2024)

Dynamic Set Cover with Worst-Case Recourse
por: Solomon, Shay, et al.
Publicado: (2025)

Nearly Optimal Internal Dictionary Matching
por: Chen, Jingbang, et al.
Publicado: (2023)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
por: Jang, Jihoon, et al.
Publicado: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
por: Dai, Jiangqi, et al.
Publicado: (2025)

Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy
por: Wang, Kaixin, et al.
Publicado: (2026)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
por: Larsen, Kasper Green, et al.
Publicado: (2023)

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

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

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

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

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

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
por: van der Hoog, Ivor, et al.
Publicado: (2025)

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

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

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
por: Silwal, Sandeep, et al.
Publicado: (2025)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
por: Mazziane, Younes Ben, et al.
Publicado: (2024)

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

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
por: Iacono, John, et al.
Publicado: (2025)

Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach
por: Li, Cheng, et al.
Publicado: (2025)