Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR03-082 | 22nd November 2003
Andris Ambainis, Ke Yang

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>


TR03-081 | 10th October 2003
Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

Computation of the Lov\'asz Theta Function for Circulant Graphs

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>


TR03-080 | 12th November 2003
Venkatesan Guruswami

Better Extractors for Better Codes?

We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint