文章基本信息

标题：Linear Consistency Testing
本地全文：下载
作者：Yonatan Aumann ; Johan Hastad ; Michael O. Rabin 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are ``linear'' if their graphs form straight lines on the plane. Two such functions are ``consistent'' if the lines have the same slope. We propose a variant of a test of Blum, Luby and Rubinfeld to check the linear-consistency of three functions f1f2f3 mapping a finite Abelian group G to an Abelian group H: Pick xyG uniformly and independently at random and check if f1(x)+f2(y)=f3(x+y). We analyze this test for two cases: (1) G and H are arbitrary Abelian groups and (2) G=\Fn2 and H=\F2. Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs (and in particular in the work of Hastad). It is abstracted explicitly for the first time here. We give an application of this problem (and of our results): A (yet another) new and tight characterization of NP, namely \e0 NP=MIP1−\e12[O(logn)31]. I.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(logn) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1−\e and rejects non-instances with probability at least 12 . Such a result is of some interest in the study of probabilistically checkable proofs.
关键词：Interactive proofs, linearity testing, Probabilistically Checkable Proofs, program checking