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

摘要

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.