TR99-025 Authors: Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan

Publication: 5th July 1999 10:01

Downloads: 2538

Keywords:

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

$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.