Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Subdistribution bounds:
TR07-064 | 19th June 2007
Rahul Jain, Hartmut Klauck, Ashwin Nayak

Direct Product Theorems for Communication Complexity via Subdistribution Bounds

A basic question in complexity theory is whether the computational
resources required for solving k independent instances of the same
problem scale as k times the resources required for one instance.
We investigate this question in various models of classical
communication complexity.

We define a new measure, the subdistribution bound, ... more >>>

ISSN 1433-8092 | Imprint