Copertina

Tight Static Lower Bounds for Non-Adaptive Data Structures

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Persiano, Giuseppe, Yeo, Kevin
Natura:	Preprint
Pubblicazione:	2020
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Differentially Private Set Representations
di: Patel, Sarvar, et al.
Pubblicazione: (2025)

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

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

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
di: Cheng, Yu, et al.
Pubblicazione: (2024)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
di: Nielsen, Mads Anker, et al.
Pubblicazione: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
di: Bringmann, Karl, et al.
Pubblicazione: (2026)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
di: Shah, Vihan
Pubblicazione: (2026)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
di: Geng, Yutong, et al.
Pubblicazione: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Non-Signaling Locality Lower Bounds for Dominating Set
di: Fleming, Noah, et al.
Pubblicazione: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

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

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

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
di: Cohen, Edith, et al.
Pubblicazione: (2024)

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

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

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

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
di: Rapoport, Emma, et al.
Pubblicazione: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

A Tight Lower Bound for Comparison-Based Quantile Summaries
di: Cormode, Graham, et al.
Pubblicazione: (2019)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
di: Shiran, Maryam
Pubblicazione: (2025)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
di: Atalig, Sunny, et al.
Pubblicazione: (2024)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
di: Kosolobov, Dmitry
Pubblicazione: (2024)

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

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

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
di: Fahrbach, Matthew, et al.
Pubblicazione: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
di: Wlodarczyk, Michal
Pubblicazione: (2023)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
di: Das, Syamantak, et al.
Pubblicazione: (2024)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
di: Räcke, Harald, et al.
Pubblicazione: (2024)

Lower Bounds on Adaptive Sensing for Matrix Recovery
di: Kacham, Praneeth, et al.
Pubblicazione: (2023)

Tight Bounds for Sampling q-Colorings via Coupling from the Past
di: Ding, Tianxing, et al.
Pubblicazione: (2025)

Tight Bounds for Gaussian Mean Estimation under Personalized Differential Privacy
di: Dong, Wei, et al.
Pubblicazione: (2026)

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

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
di: Mahpud, Bar, et al.
Pubblicazione: (2025)