Improved direct product theorems for randomized query complexity

DOI10.1007/S00037-012-0043-7MaRDI QIDQ693002zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

decision treesquery complexityaverage-case complexityhardness amplificationdirect product theorems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Towards proving strong direct product theorems
• A strong direct product theorem for quantum query complexity
• A composition theorem for randomized query complexity

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)