Oleg Verbitsky

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 >>>

Oded Goldreich, Guy Rothblum

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 >>>