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

DOI10.1137/05063235XzbMath1123.68045WikidataQ58040231 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

Related Items (19)

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 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