Theory of Computing
-------------------
Title : Competing-Provers Protocols for Circuit Evaluation
Authors : Gillat Kol and Ran Raz
Volume : 10
Number : 5
Pages : 107-131
URL : https://theoryofcomputing.org/articles/v010a005
Abstract
--------
Let $C$ be a (fan-in 2) Boolean circuit of size $s$ and depth $d$,
and let $x$ be an input for $C$. Assume that a verifier, that knows
$C$ but does not know $x$, can access the low degree extension of $x$
at one random point. Two competing provers try to convince the
verifier that $C(x)=0$ and $C(x)=1$, respectively, and it is assumed
that one of the provers is honest.
For any $r\geq1$, we construct* an $r$-round protocol with communication
complexity $d^{1/r}\polylog(s)$ that convinces the
verifier of the correct value of $C(x)$ (with small probability of
error). In particular, when we allow only one round, the protocol
exchanges $d.\polylog(s)$ bits, and when we allow
$r=O(\log(d)/\log\log(s))$
rounds, the protocol exchanges only $\polylog(s)$ bits.
Moreover, the complexity of the verifier and honest prover in this
protocol is $\poly(s)$, and if in addition the circuit is
$\log(s)$-space uniform, the complexity of the verifier is
$d^{1/r}\polylog(s)$.
The protocol is obtained by combining the _delegation protocol_ of
Goldwasser, Kalai, and Rothblum (STOC 2008), the _competing-provers
protocols_ of Feige and Kilian (STOC 1997), and some new techniques.
We suggest two applications of these results:
Delegating computation to competing clouds: The main motivation
behind the protocol of GKR'08 was _delegating computation
_to a cloud_. Using our new protocol, a verifier can delegate
computation to two (or more) competing clouds. If at least one of
the clouds is reliable the verifier can trust that the computation
is correct (with high probability). The advantage over the
protocol of GKR'08 is that the communication complexity and
the number of rounds in our protocol are significantly lower.
Communication complexity with competing provers, and circuit lower
bounds: Aaronson and Wigderson (2009) suggested the model of
communication complexity with competing provers, where two
competing provers try to convince two players that $f(x,y)=0$ and
$f(x,y)=1$, respectively, where $x$ is an input held by the first
player and $y$ is an input held by the second player. By scaling
down the competing-provers protocols of FK'97, they showed
that strong enough lower bounds for the communication complexity
of $f$, in this model, imply lower bounds for the computational
complexity of $f$.
Our results strengthen this connection. More precisely, we show
that if $f$ can be computed by a Boolean circuit of size $s$ and
depth $d$ then for any $r\geq 1$ there is an $r$-round protocol for
$f$, in this model, with communication complexity
$d^{1/r}\polylog(s)$. This can be viewed as a
possible direction towards proving circuit lower bounds. For
instance, in order to prove $f\notin\NC$, it suffices to show that
any one round protocol for $f$, in this model, requires the
exchange of $\omega(\polylog(n))$
bits. This gives a relatively simple combinatorial property that
implies strong circuit lower bounds.
-------------
A conference version of this paper appeared in the Proceedings of the
4th Innovations in Theoretical Computer Science Conference (ITCS), 2013.
* We have learned that a result similar to ours for the case $r=1$,
as well as the motivation of delegating computation to competing
clouds, was independently obtained by Canetti, Riva, and Rothblum
(ICITS 2012).