The Power of Distributed Verifiers in Interactive Proofs
share
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 messages. The goal is to verify that the graph G belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size. This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of non-interactive distributed proofs. 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 Ω(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 to ones where the verifier is distributed with short proof size. We show the following: * Every (centralized) computation that can be performed in time O(n) can be translated into three-round distributed interactive protocol with O( n) proof size. This implies that many graph problems for sparse graphs have succinct proofs. * Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with O(1) rounds and O( n) bits proof size for the low space case and polylog(n) many rounds and proof size for NC. * We show that for Graph Non-Isomorphism, there is a 4-round protocol with O( n) proof size, improving upon the O(n n) proof size of Kol et al. * For many problems we show how to reduce proof size below the naturally seeming barrier of n. We get a 5-round protocols with proof size O( n) for a family of problems.
READ FULL TEXT