TY - JOUR
T1 - Competing-provers protocols for circuit evaluation
AU - Kol, Gillat
AU - Raz, Ran
N1 - Funding Information:
A conference version of this paper appeared in the Proceedings of the 4th Innovations in Theoretical Computer Science conference (ITCS), 2013 [8]. †Research supported by Israel Science Foundation (ISF) grant. ‡Research supported by Israel Science Foundation (ISF) grant. 1We 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).
Publisher Copyright:
© 2014 Gillat Kol and Ran Raz.
PY - 2014/8/9
Y1 - 2014/8/9
N2 - 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 ≥ 1, we construct1 an r-round protocol with communication complexity d1/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 the 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 d1/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 ≥ 1 there is an r-round protocol for f, in this model, with communication complexity d1/r polylog (s). This can be viewed as a possible direction towards proving circuit lower bounds. For instance, in order to prove f ϵ NC, it suffices to show that any one-round protocol for f, in this model, requires the exchange of ω (polylog (n)) bits. This gives a relatively simple combinatorial property that implies strong circuit lower bounds.
AB - 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 ≥ 1, we construct1 an r-round protocol with communication complexity d1/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 the 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 d1/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 ≥ 1 there is an r-round protocol for f, in this model, with communication complexity d1/r polylog (s). This can be viewed as a possible direction towards proving circuit lower bounds. For instance, in order to prove f ϵ NC, it suffices to show that any one-round protocol for f, in this model, requires the exchange of ω (polylog (n)) bits. This gives a relatively simple combinatorial property that implies strong circuit lower bounds.
KW - Communication complexity
KW - Competing provers
KW - Complexity theory
KW - Delegation
UR - http://www.scopus.com/inward/record.url?scp=85032816854&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032816854&partnerID=8YFLogxK
U2 - 10.4086/toc.2014.v010a005
DO - 10.4086/toc.2014.v010a005
M3 - Article
AN - SCOPUS:85032816854
SN - 1557-2862
VL - 10
SP - 107
EP - 131
JO - Theory of Computing
JF - Theory of Computing
ER -