Linear-consistency testing

We extend the notion of linearity testing to the task of checking linear co nsistency of multiple functions. Informally, functions are "linear" if thei r graphs form straight lines on the plane. Two such functions are "consiste nt" if the lines have the same slope. We propose a variant of a test of M. Blum et al. (J. Comput. System Sci. 47 (1993), 549-595) to check the linear consistency of three functions f(1). f(2). f(3) mapping a finite Abelian g roup G to an Abelian group H: Pick x, y is an element of G uniformly and in dependently at random and check if f(1)(x) + f(2)(y) = f(3)(x + y). We anal yze 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-c onsistency testing seem to hav e been implicitly considered in recent work on the construction of PCPs and in particular in the work of J. Hastad [9] (in "Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Comp uting. El Paso. Texas, 4-6 May 1997," pp. 1-10). It is abstracted explicitl y for the first time here. As an application of our results we give yet ano ther new and tight characterization of NP. namely For All epsilon > 0, NP = MIP1-epsilon 1/2 [O(log n), 3, 1]. That is, every language in NP has 3-pro ver 1-round proof systems in which the verifier tosses O(log n) coins and a sks each of the three provers one question each. The provers respond with o ne bit each such that the verifier accepts instance of the language with pr obability 1 - epsilon and rejects noninstances with probability at least;. Such a result is of some interest in the study of probabilistically checkab le proofs. (C) 2001 Acadamic Press.