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

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

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

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which

1. The query-complexity of verification is significantly smaller than the query-complexity of testing.

2. The query-complexity of the ... more >>>

We investigate two resources whose effects on quantum interactive proofs remain poorly understood: the promise of unentanglement, and the verifier’s ability to condition on an intermediate measurement, which we call post-measurement branching. We first show that unentanglement can dramatically increase computational power: three-round unentangled quantum interactive proofs equal NEXP, even ... more >>>

Interactive proofs of proximity for distributions, introduced by Chiesa and Gur (ITCS18) and extensively studied recently by Herman and Rothblum (STOC22, FOCS23, FOCS24}, offer a way of verifying properties of distributions using less samples than required to test these properties.

We say that such an interactive proof system is {\sf ... more >>>

We consider interactive proofs for the promise problem, called $\epsilon$-FARNESS, in which the yes-instances are pairs of distributions over $[n]$ that are $\epsilon$-far from one another, and the no-instances are pairs of identical distributions.
For any $t\leq n^{2/3}$, we obtain an interactive proof in which the verifier has sample complexity ... more >>>