Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXTREMAL FINITE SET THEORY WARNING: DO NOT SEND LONG UNAUTHORIZED FILES TO THE ABOVE ADDRESS:
Reports tagged with extremal finite set theory Warning: DO NOT SEND LONG UNAUTHORIZED FILES TO THE ABOVE ADDRESS:
TR95-013 | 24th February 1995
Oleg Verbitsky

The Parallel Repetition Conjecture for Trees is True


The parallel repetition conjecture (PRC) of Feige and Lovasz says that the
error probability of a two prover one round interactive protocol repeated $n$
times in parallel is exponentially small in $n$.
We show that the PRC is true in the case when
the bipartite graph of dependence between ... more >>>




ISSN 1433-8092 | Imprint