Recycling queries in PCPs and in linearity tests (extended abstract)
Luca Trevisan · 1998
WC study query-efficient Probabilistically Checkable Proofs (PCPs) and linearity tests.We focus on the number of amor- rlzed query bits, A testing algorithm uses g amortized query bita if, for some constant k, it reads qh bits and has error probability at most 2 'I;, The best known PCP construction for NP in this respect uses 3 amortized query bits [13]; at least one amortized query bit is necessary, unless P = NP [S], This parameter is a fairly natural one and has applications to proving non-approximability results for constraint satisfaction problems, Furthermore, a PCP characterization of NP with less than 2 amortized query bits implies a separation of the PCP model from the 2-Prover l-Round model.Our approach is to take an atomic verification procedure and then iterate it several times, saving queries by recycling them between different iterations of the atomic test.We first apply this ideain order to develop query-efficient llnearlty tests, Linearity testing is a problem closely related to testing the Long Code and making PCP constructions.It in also a significant combinatorial problem still lacking tight characterizations, except for the case of three queries [4].The best known linearity test uses 3 amortized query bits 141; a different one achieves 1 amortized free bit (a different parameter related to the Max Clique problem) but uses an unbounded number of amortized query bits [5].We develop a general analysis technique and a linearity test achieving simultaneously amortized query complexity 1.5 and amortized free bit complexity .6.This test answers an open question raised by Bellare, Goldreich and Sudan.We then show how to adapt a weaker result to the PCP setting, and we obtain a PCP for NP that makes 5 queries 'MIT Luborutory for