Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Communication-space tradeoff:
TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

Quantum and Classical Strong 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 ... more >>>

ISSN 1433-8092 | Imprint