Improved direct product theorems for randomized query complexity
From MaRDI portal
Publication:693002
DOI10.1007/S00037-012-0043-7zbMATH Open1253.68147OpenAlexW2112852465MaRDI QIDQ693002FDOQ693002
Recommendations
Cites work
- 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 2086702 (Why is no real title available?)
- A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- A strong direct product theorem for disjointness
- A strong direct product theorem for quantum query complexity
- CREW PRAM<scp>s</scp> and Decision Trees
- Complexity measures and decision tree complexity: a survey.
- Computing with Noisy Information
- Concentration of Measure for the Analysis of Randomized Algorithms
- Constructive proofs of concentration bounds
- General hardness amplification of predicates and puzzles. (Extended abstract)
- Indistinguishability Amplification
- Key agreement from weak bit agreement
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Products and Help Bits in Decision Trees
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Robust polynomials and quantum algorithms
- Towards proving strong direct product theorems
- Uniform direct product theorems: simplified, optimized, and derandomized
Cited in
(11)- A direct product theorem for two-party bounded-round public-coin communication complexity
- Tight characterizations for preprocessing against cryptographic salting
- Lifting Theorems for Equality
- Simulation theorems via pseudo-random properties
- Query-to-communication lifting using low-discrepancy gadgets
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Towards proving strong direct product theorems
- A composition theorem for randomized query complexity
- Uniform direct product theorems: simplified, optimized, and derandomized
- Forrelation: a problem that optimally separates quantum from classical computing
- Optimal separation and strong direct sum for randomized query complexity
This page was built for publication: Improved direct product theorems for randomized query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693002)
