Improved direct product theorems for randomized query complexity
From MaRDI portal
Publication:693002
DOI10.1007/S00037-012-0043-7zbMATH Open1253.68147OpenAlexW2112852465MaRDI QIDQ693002FDOQ693002
Authors: Andrew Drucker 
Publication date: 7 December 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0043-7
Recommendations
- Strong direct product theorems for quantum communication and query complexity
- Strong direct product theorems for quantum communication and query complexity
- Towards proving strong direct product theorems
- A strong direct product theorem for quantum query complexity
- A composition theorem for randomized query complexity
Cites Work
- Computing with Noisy Information
- Title not available (Why is that?)
- Concentration of Measure for the Analysis of Randomized Algorithms
- CREW PRAM<scp>s</scp> and Decision Trees
- Title not available (Why is that?)
- Complexity measures and decision tree complexity: a survey.
- Key agreement from weak bit agreement
- Title not available (Why is that?)
- Towards proving strong direct product theorems
- A strong direct product theorem for disjointness
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- A strong direct product theorem for quantum query complexity
- Products and Help Bits in Decision Trees
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
- Robust polynomials and quantum algorithms
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Indistinguishability Amplification
- General hardness amplification of predicates and puzzles. (Extended abstract)
- Uniform direct product theorems: simplified, optimized, and derandomized
- Constructive proofs of concentration bounds
Cited In (10)
- Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Simulation theorems via pseudo-random properties
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- Uniform direct product theorems: simplified, optimized, and derandomized
- Title not available (Why is that?)
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Tight characterizations for preprocessing against cryptographic salting
- Lifting Theorems for Equality
- Towards proving strong direct product theorems
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)
