ECCC-Report TR99-025https://eccc.weizmann.ac.il/report/1999/025Comments and Revisions published for TR99-025en-usMon, 05 Jul 1999 10:01:14 +0300
Paper TR99-025
| Linear Consistency Testing |
Yonatan Aumann,
Johan HÃ¥stad,
Michael O. Rabin,
Madhu Sudan
https://eccc.weizmann.ac.il/report/1999/025We 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
$f_1,f_2,f_3$ mapping a finite Abelian group $G$ to an Abelian
group $H$: Pick $x,y \in G$ uniformly and independently at random
and check if $f_1(x) + f_2(y) = f_3(x+y)$. We analyze this test
for two cases: (1) $G$ and $H$ are arbitrary Abelian groups and
(2) $G = \F_2^n$ and $H = \F_2$.
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 $\forall \e > 0, ~
NP = MIP_{1-\e,1/2} [O(\log n), 3, 1]$. I.e., every language in
NP has 3-prover 1-round proof systems in which the verifier
tosses $O(\log n)$ 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 $1/2$.
Such a result is of some interest in the study of probabilistically
checkable proofs.
Mon, 05 Jul 1999 10:01:14 +0300https://eccc.weizmann.ac.il/report/1999/025