Competing provers protocols for circuit evaluation

Gillat Kol, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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 doesn't 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 assume that one of the provers is honest. For any r≥1, we give an r rounds protocol with communication complexity d1/r poly log(s) that convinces the verifier in the correct value of C(x) (with small probability of error). In particular, when we allow only one round, the protocol exchanges d · poly log(s) bits, and when we allow r=O(log(d)/log log(s)) rounds, the protocol exchanges only poly log(s) bits. Moreover, the complexity of the verifier and honest provers 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 poly log(s). The protocol is obtained by combining the delegation protocol of Goldwasser, Kalai and Rothblum [5] and the competing provers protocols of Feige and Kilian [3] and some new techniques. We suggest two applications of these results: Delegating computation to competing clouds: The main motivation behind the protocol of [5] 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 [5] 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 [1] 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 [3], 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 rounds protocol for f, in this model, with communication complexity d 1/r poly log(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 w(poly log(n)) bits. This gives a relatively simple combinatorial property that implies strong circuit lower bounds.

Original languageEnglish (US)
Title of host publicationITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages473-484
Number of pages12
DOIs
StatePublished - Feb 11 2013
Externally publishedYes
Event2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States
Duration: Jan 9 2013Jan 12 2013

Publication series

NameITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Other

Other2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
CountryUnited States
CityBerkeley, CA
Period1/9/131/12/13

All Science Journal Classification (ASJC) codes

  • Management of Technology and Innovation
  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Competing provers protocols for circuit evaluation'. Together they form a unique fingerprint.

  • Cite this

    Kol, G., & Raz, R. (2013). Competing provers protocols for circuit evaluation. In ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science (pp. 473-484). (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science). https://doi.org/10.1145/2422436.2422487