Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-069 | 16th April 2018 18:39

Constant-round interactive proof systems for AC0[2] and NC1

RSS-Feed




Revision #1
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 16th April 2018 18:39
Downloads: 840
Keywords: 


Abstract:

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more relaxed notion of uniformity and offers a better trade-off between the number of rounds and the round complexity that our proof system for NC1.
We observe that all three aforementioned systems yield constant-round doubly-efficient proof systems for the All-Pairs Shortest Paths problem.



Changes to previous version:

Correcting a typo in Cor 2 and adding a reference to [11].


Paper:

TR18-069 | 14th April 2018 21:42

Constant-round interactive proof systems for AC0[2] and NC1





TR18-069
Authors: Oded Goldreich, Guy Rothblum
Publication: 14th April 2018 21:42
Downloads: 928
Keywords: 


Abstract:

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more relaxed notion of uniformity and offers
a better trade-off between the number of rounds and the round complexity that our proof system for NC1.
We observe that all three aforementioned systems yield constant-round doubly-efficient proof systems for the All-Pairs Shortest Paths problem.



ISSN 1433-8092 | Imprint