Cover Image

A Strong Direct Sum Theorem for Distributional Query Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blanc, Guy, Koch, Caleb, Strassle, Carmen, Tan, Li-Yang
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
by: Guruswami, Venkatesan, et al.
Published: (2025)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
by: Herman, Tal, et al.
Published: (2024)

Strong XOR Lemma for Information Complexity
by: Sawettamalya, Pachara, et al.
Published: (2024)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
by: Kortsarz, Guy
Published: (2026)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

Geometry Of The Subset Sum Problem -- Part I
by: Bollepalli, Srinivas Balaji
Published: (2025)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)