Competing-Provers Protocols for Circuit Evaluation

by Gillat Kol and Ran Raz

Theory of Computing, Volume 10(5), pp. 107-131, 2014

Bibliography with links to cited articles

[1]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. on Computation Theory, 1(1):2, 2009. Preliminary version in STOC’08. See also at ECCC. [doi:10.1145/1490270.1490272]

[2]   Ran Canetti, Ben Riva, and Guy N. Rothblum: Refereed delegation of computation. Inform. and Comput., 226:16–36, 2013. Preliminary version in ICITS’12. See also at Cryptology ePrint Archive. [doi:10.1016/j.ic.2013.03.003]

[3]   Uriel Feige and Joe Kilian: Making games short (extended abstract). In Proc. 29th STOC, pp. 506–516. ACM Press, 1997. [doi:10.1145/258533.258644]

[4]   Uriel Feige, Adi Shamir, and Moshe Tennenholtz: The noisy oracle problem. In Proc. 8th Ann. Internat. Crypto. Conf. (CRYPTO’88), volume 403 of LNCS, pp. 284–296, 1988. [doi:10.1007/0-387-34799-2_22]

[5]   Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum: Delegating computation: interactive proofs for muggles. In Proc. 40th STOC, pp. 113–122. ACM Press, 2008. [doi:10.1145/1374376.1374396]

[6]   Yael Tauman Kalai and Ran Raz: Interactive PCP. In Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), volume 5126 of LNCS, pp. 536–547. Springer, 2008. See also at ECCC. [doi:10.1007/978-3-540-70583-3_44]

[7]   Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum: How to delegate computations: The power of no-signaling proofs. In Proc. 46th STOC, pp. 485–494. ACM Press, 2014. See also at ECCC. [doi:10.1145/2591796.2591809]

[8]   Gillat Kol and Ran Raz: Competing provers protocols for circuit evaluation. In Proc. 4th Symp. Innovations in Theoretical Computer Science (ITCS’13), pp. 473–484. ACM Press, 2013. See also at ECCC. [doi:10.1145/2422436.2422487]

[9]   Daphne Koller and Nimrod Megiddo: The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528–552, 1992. [doi:10.1016/0899-8256(92)90035-Q]

[10]   Guy N. Rothblum: Delegating Computation Reliably: Paradigms and Constructions. Ph. D. thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. DSpace@MIT.