Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Marc Kaplan:

TR08-109 | 10th November 2008
Marc Kaplan, Sophie Laplante

Kolmogorov complexity and combinatorial methods in communication complexity

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

ISSN 1433-8092 | Imprint