Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs

DOI10.1137/05063235XzbMath1123.68045DBLPjournals/siamcomp/KlauckSW07WikidataQ58040231 ScholiaQ58040231MaRDI QIDQ5422496

Robert Špalek, Hartmut Klauck, Ronald de Wolf

Publication date: 22 October 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsquantum computingdecision treescommunication complexitycomplexity theory

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ A discrepancy lower bound for information complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ A strong direct product theorem for quantum query complexity ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Algorithmic Polynomials ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item ⋮ The NISQ complexity of collision finding ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

This page was built for publication: Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs