אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short message. The goal is to verify that the graph $G$ belongs to some language in a small number of rounds, and with small communication bound, \ie the proof size.

This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of non-interactive distributed proof. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism -- both of which require proofs of $\Omega(n^2)$-bits without interaction.

In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm runs by the centralized verifier. We show the following:

* Every public-coin protocol in the standard model with a verifier that runs in time $O(n)$ can be translated into a distributed IP protocol that preserves the number rounds plus two, and with $O(\log n)$ proof size. This implies that many graph problems for sparse graphs have succinct proofs (\eg testing planarity).

* We also demonstrate the power of the compiler for dense graphs as well. We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with $O(\log n)$ proof size, improving upon the $O(n \log n)$ proof size of Kol et al.

* Using even more rounds of interaction, we show how to reduce the proof size below the natural barrier of $\log n$. By employing our RAM compiler, we get a 5-round protocols with proof size $O(\log \log n)$ for a family of problems including \eg $k$-Clique, Fixed Automorphism and Leader Election.

* Finally, we consider protocols with polylogarithmic (in $n$) many rounds. In this regime, we present a general compiler that transforms any standard protocol where the verifier can be implemented by an NC circuit (polylogarithmic depth and polynomial size) to a distributed protocol with polylogarithmic many rounds and proof size. This compiler captures many natural problems and demonstrates the difficultly in showing lower bounds for this regime.

Joint work with Merav Parter and Moni Naor