Improved direct product theorems for randomized query complexity

DOI10.1007/S00037-012-0043-7zbMath1253.68147OpenAlexW2112852465MaRDI QIDQ693002

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 treeshardness amplificationaverage-case complexityquery complexitydirect product theorems

Mathematics Subject Classification ID

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

Related Items (8)

A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ Tight characterizations for preprocessing against cryptographic salting ⋮ Lifting Theorems for Equality ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong direct product theorem for quantum query complexity
• Optimal direct sum results for deterministic and randomized decision tree complexity
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Complexity measures and decision tree complexity: a survey.
• Towards proving strong direct product theorems
• Robust polynomials and quantum algorithms
• A strong direct product theorem for disjointness
• General Hardness Amplification of Predicates and Puzzles
• Key agreement from weak bit agreement
• Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
• Constructive Proofs of Concentration Bounds
• Indistinguishability Amplification
• CREW PRAM<scp>s</scp> and Decision Trees
• Products and Help Bits in Decision Trees
• Computing with Noisy Information
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Improved direct product theorems for randomized query complexity