Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-013 | 24th February 1995 00:00

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 queries to provers is a tree.
Previously this was known only in the case of complete bipartite graphs
(i.e. when the queries to provers are independent).
We suggest also the combinatorial characterization of method
that was used to obtain most results towards the PRC and discuss some
related combinatorial problems.

ISSN 1433-8092 | Imprint