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

Oded Goldreich, Guy Rothblum, Tal Skverer

Interactive proofs of proximity (IPPs) offer ultra-fast

approximate verification of assertions regarding their input,

where ultra-fast means that only a small portion of the input is read

and approximate verification is analogous to the notion of

approximate decision that underlies property testing.

Specifically, in an IPP, the prover can make ...
more >>>