All reports by Author Robert Spalek:

__
TR04-045
| 15th April 2004
__

Hartmut Klauck, Robert Spalek, Ronald de Wolf#### Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

Hartmut Klauck, Robert Spalek, Ronald de Wolf

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