✍ Scribed by Yonatan Aumann; Johan Håstad; Michael O. Rabin; Madhu Sudan
No coin nor oath required. For personal study only.
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 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 group G to an Abelian group H: Pick x, y # 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 n 2 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 J. Ha# stad [9] (in ``Proceedings of the Twenty-Ninth
📜 SIMILAR VOLUMES
A new multicomponent consistency test is proposed that examines experimental results in pairs. The method simplifies the locating of random errors and enabks the results to be tested for consistency as determined.