Constant-round interactive proof systems for AC0[2] and NC1
Constant-round interactive proof systems for AC0[2] and NC1
复制标题
AC0[2] 和 NC1 的恒轮交互式证明系统
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Rothblum
中科院分区：
文献类型：
--
作者：
Oded Goldreich;G. Rothblum
我们为（mathcal{AC}^0[2]）和（mathcal{NC}^1）的充分统一版本提出了常数轮交互式证明系统。这两个证明系统都是双重有效的，并且在轮复杂性和总通信之间提供了比Reingold，Rothblum和Rothblum的工作更好的权衡（STOC，2016）。我们的（mathcal{AC}^0[2]）证明系统支持更宽松的一致性概念，并在轮数和轮复杂度之间提供了更好的权衡，我们的证明系统（mathcal{NC}^1）。我们观察到，所有上述三个系统产生恒定轮双有效的证明系统的所有对最短路径问题。
We present constant-round interactive proof systems for sufficiently uniform versions of (mathcal{AC}^0[2]) and (mathcal{NC}^1). 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 (mathcal{AC}^0[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 (mathcal{NC}^1). We observe that all three aforementioned systems yield constant-round doubly-efficient proof systems for the All-Pairs Shortest Paths problem.