Improved direct product theorems for randomized query complexity
From MaRDI portal
(Redirected from Publication:693002)
Recommendations
Cites work
- 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
- A strong direct product theorem for disjointness
- A strong direct product theorem for quantum query complexity
- 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
- CREW PRAM<scp>s</scp> and Decision Trees
- General hardness amplification of predicates and puzzles. (Extended abstract)
- 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?)
- 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
(14)- Towards proving strong direct product theorems
- Simulation theorems via pseudo-random properties
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Uniform direct product theorems: simplified, optimized, and derandomized
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Forrelation: a problem that optimally separates quantum from classical computing
- Lifting Theorems for Equality
- Optimal separation and strong direct sum for randomized query complexity
- A composition theorem for randomized query complexity
- Query-to-communication lifting using low-discrepancy gadgets
- Tight characterizations for preprocessing against cryptographic salting
- A strong direct sum theorem for distributional query complexity
- A technique for hardness amplification against AC^0
- A strong direct sum theorem for distributional 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)
