Cover Image

Direct Product Theorems for Randomized Query Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ben-David, Shalev, Blais, Eric
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

Separations in query complexity for total search problems
by: Ben-David, Shalev, et al.
Published: (2024)

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

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)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

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

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

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

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

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

Lines in Every Direction with No ee-Random Points
by: Lutz, Neil, et al.
Published: (2025)

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

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
by: Bodlaender, Hans L., et al.
Published: (2026)

Characterizing Direct Product Testing via Coboundary Expansion
by: Bafna, Mitali, et al.
Published: (2023)

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

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

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

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

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

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

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
by: Goertzel, Ben, et al.
Published: (2026)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Modifications of Quantum Computation and Adaptive Queries to PP
by: Miloschewsky, David, et al.
Published: (2025)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)

Random Unitaries in Constant (Quantum) Time
by: Foxman, Ben, et al.
Published: (2025)

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

A Refinement of the McCreight-Meyer Union Theorem
by: Fox, Matthew, et al.
Published: (2024)

Complexity of adaptive testing in scenarios defined extensionally
by: Rodriguez, Ismael, et al.
Published: (2026)

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
by: Li, Zihan, et al.
Published: (2024)