## Ronald de Wolf

*Direct Product Theorems and Optimal Time-Space Tradeoffs*A strong direct product theorem says that if we want to compute k
independent instances of a function, using less than k times the
resources needed for one instance, then our overall success
probability will be exponentially small in k. We establish such
theorems for the classical as well as quantum query complexity of the
OR function. This implies slightly weaker direct product results for
all total functions. We prove a similar result for quantum
communication protocols computing k instances of the Disjointness
function.

Our direct product theorems imply a time-space tradeoff
T^2*S=Omega(N^3) for sorting N items on a quantum computer, which is
optimal up to polylog factors. They also give several tight time-space
and communication-space tradeoffs for the problems of Boolean
matrix-vector multiplication and matrix multiplication.

Joint work with Hartmut Klauck and Robert Spalek
quant-ph/0402123