Copertina

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Garg, Sumegha, Hastings, Jabari, Pabbaraju, Chirag, Sharan, Vatsal
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

The Sample Complexity of Replicable Realizable PAC Learning
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)

A New Information Complexity Measure for Multi-pass Streaming with Applications
di: Braverman, Mark, et al.
Pubblicazione: (2024)

Efficient Convex Optimization Requires Superlinear Memory
di: Marsden, Annie, et al.
Pubblicazione: (2022)

Near Optimal Alphabet-Soundness Tradeoff PCPs
di: Minzer, Dor, et al.
Pubblicazione: (2024)

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

On optimal distinguishers for Planted Clique
di: Nagda, Ansh, et al.
Pubblicazione: (2025)

Transductive Learning Is Compact
di: Asilis, Julian, et al.
Pubblicazione: (2024)

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
di: Chen, Yu-Zhen Janice, et al.
Pubblicazione: (2025)

Computational-Statistical Tradeoffs from NP-hardness
di: Blanc, Guy, et al.
Pubblicazione: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

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

Frontier Space-Time Algorithms Using Only Full Memory
di: Chmel, Petr, et al.
Pubblicazione: (2026)

New and Improved Bounds for Markov Paging
di: Pabbaraju, Chirag, et al.
Pubblicazione: (2025)

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

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 Faster Randomized Algorithm for Vertex Cover: An Automated Approach
di: Clinch, Katie, et al.
Pubblicazione: (2025)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
di: Blanchard, Moise
Pubblicazione: (2024)

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

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

Structural Parameters for Steiner Orientation
di: Hanaka, Tesshu, et al.
Pubblicazione: (2025)

Detecting Low-Degree Truncation
di: De, Anindya, et al.
Pubblicazione: (2024)

The Structure of In-Place Space-Bounded Computation
di: Cook, James, et al.
Pubblicazione: (2025)

Structural Parameterizations for Induced and Acyclic Matching
di: Lampis, Michael, et al.
Pubblicazione: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
di: Greilhuber, Jakob, et al.
Pubblicazione: (2026)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
di: Yu, Xifan, et al.
Pubblicazione: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
di: Lampis, Michael, et al.
Pubblicazione: (2023)

Fine-Grained Classification Of Detecting Dominating Patterns
di: Dransfeld, Jonathan, et al.
Pubblicazione: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
di: de Berg, Mark, et al.
Pubblicazione: (2025)

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

Testing with Non-identically Distributed Samples
di: Garg, Shivam, et al.
Pubblicazione: (2023)

A Characterization of List Regression
di: Pabbaraju, Chirag, et al.
Pubblicazione: (2024)

The Planted Orthogonal Vectors Problem
di: Kühnemann, David, et al.
Pubblicazione: (2025)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
di: Charikar, Moses, et al.
Pubblicazione: (2023)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
di: Chen, Sitan, et al.
Pubblicazione: (2026)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
di: Zhan, Yongjian
Pubblicazione: (2026)

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

A Simple Proof that Ricochet Robots is PSPACE-Complete
di: Balanza-Martinez, Jose, et al.
Pubblicazione: (2024)