Revised: May 18, 2014

Published: August 9, 2014

**Keywords:**communication complexity, competing provers, delegation, complexity theory

**Categories:**complexity theory, communication complexity, Boolean circuits, circuit complexity, circuit value, provers, competing provers

**ACM Classification:**H.4, F.0

**AMS Classification:**68Q10, 68Q15

**Abstract:**
[Plain Text Version]

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^{1}
an $r$-round protocol with communication
complexity $d^{1/r}\poly\log\left(s\right)$ 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\cdot\poly\log\left(s\right)$ bits, and when we allow
$r=O\left(\frac{\log\left(d\right)}{\log\log\left(s\right)}\right)$
rounds, the protocol exchanges only $\poly\log\left(s\right)$ 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}\poly\log\left(s\right)$.
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 GTR'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\geq1$ there is an $r$-round protocol for $f$, in this model, with communication complexity $d^{1/r}\poly\log\left(s\right)$. 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\left(\poly\log\left(n\right)\right)$ 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.

^{1}
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).