文章基本信息

标题：On Interactive Proofs with a Laconic Prover
本地全文：下载
作者：Oded Goldreich ; Salil Vadhan ; Avi Wigderson. 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich and Hastad (IPL 1998). Let L be a language that has an interactive proof in which the prover sends few (say b ) bits to the verifier. We prove that the complement L has a {\em constant-round} interactive proof of complexity that depends only exponentially on b . This provides the first evidence that for \NP -complete languages, we cannot expect interactive provers to be much more ``laconic'' than the standard \NP proof. When the proof system is further restricted (eg when b = 1 , or when we have perfect completeness), we get significantly better upper bounds on the complexity of L .
关键词：Arthur-Merlin games , Game Theory , Interactive proofs , sampling protocols , statistical zero knowledge