Copertina

On the Advantage of Adaptivity for Sampling with Cell Probes

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Byramji, Farzan, Kane, Daniel M., Morris, Jackson, Ostuni, Anthony
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Locality Bounds for Sampling Hamming Slices
di: Kane, Daniel M., et al.
Pubblicazione: (2024)

Hard-to-Sample Distributions from Robust Extractors
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

Sampling Permutations with Cell Probes is Hard
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
di: Ko, Young Kun
Pubblicazione: (2025)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
di: Yoshida, Yuichi, et al.
Pubblicazione: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
di: Garg, Sumegha, et al.
Pubblicazione: (2026)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
di: Dumas, Maël, et al.
Pubblicazione: (2022)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
di: Kocurek, Nicholas, et al.
Pubblicazione: (2026)

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
di: Bogdanov, Andrej, et al.
Pubblicazione: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
di: Ye, Daniel
Pubblicazione: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
di: Moka, Sarat, et al.
Pubblicazione: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
di: Esmer, Barış Can, et al.
Pubblicazione: (2025)

On the Space Complexity of Online Convolution
di: Andersson, Joel Daniel, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
di: Curticapean, Radu, et al.
Pubblicazione: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
di: Lanzinger, Matthias, et al.
Pubblicazione: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
di: Döring, Simon, et al.
Pubblicazione: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
di: Focke, Jacob, et al.
Pubblicazione: (2022)

Can You Link Up With Treewidth?
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
di: Focke, Jacob, et al.
Pubblicazione: (2023)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
di: Ko, Young Kun
Pubblicazione: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
di: Frei, Fabian, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
di: Frei, Fabian, et al.
Pubblicazione: (2025)

An alignment problem
di: McDaniel, Emma L., et al.
Pubblicazione: (2024)

Colouring $(P_r+P_s)$-Free Graphs
di: Klimošová, Tereza, et al.
Pubblicazione: (2018)

Improved Stabilizer Estimation via Bell Difference Sampling
di: Grewal, Sabee, et al.
Pubblicazione: (2023)

Most Juntas Saturate the Hardcore Lemma
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Broadcasting under Structural Restrictions
di: Egami, Yudai, et al.
Pubblicazione: (2025)

Linear Hashing Is Optimal
di: Jaber, Michael, et al.
Pubblicazione: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
di: Jonsson, Peter, et al.
Pubblicazione: (2025)