A strong direct sum theorem for distributional query complexity

DOI10.4230/LIPICS.CCC.2024.16MaRDI QIDQ6866480zbMATH OpenFDO

Authors Guy Blanc, Caleb M. Koch, Carmen Strassle, Li-Yang Tan

Publication date 28 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2024.16

zbMATH Keywords

direct product theoremhardcore theoremquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A direct product theorem for the two-party bounded-round public-coin communication complexity
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A strong composition theorem for junta complexity and the boosting of property testers
• A strong direct product theorem for disjointness
• A strong direct product theorem for quantum query complexity
• Boosting and hard-core set construction
• Direct products in communication complexity
• Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
• Hardness amplification within NP
• Hardness vs randomness
• How to compress interactive communication
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• scientific article; zbMATH DE number 5485571 (Why is no real title available?)
• scientific article; zbMATH DE number 7789151 (Why is no real title available?)
• Improved direct product theorems for randomized query complexity
• New strong direct product results in communication complexity
• Nondeterministic direct product reductions and the success probability of SAT solvers
• Norms, XOR lemmas, and lower bounds for polynomials and protocols
• On Yao's XOR-lemma
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Optimal separation and strong direct sum for randomized query complexity
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Strong direct product theorems for quantum communication and query complexity
• Strong XOR lemma for communication with bounded rounds (extended abstract)
• Towards proving strong direct product theorems

Cited in

(1)

• A strong direct sum theorem for distributional query complexity

This page was built for publication: A strong direct sum theorem for distributional query complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866480)