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