Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with interactive proof system:
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 >>>

TR18-069 | 14th April 2018
Oded Goldreich, Guy Rothblum

Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more ... more >>>

ISSN 1433-8092 | Imprint