Recycling Queries in PCPs and in Linearity Tests (Extended Abstract)

] LUCA TREVISAN Abstract We study query-efficient Probabilistically Checkable Proofs (PCPs) and linearity tests. We focus on the number of amortized query bits. A testing algorithm uses ¯ q amortized query bits if, for some constant k, it reads ¯ qk bits and has error probability at most 2 \Gammak . 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 [5]. 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 1-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 idea in order to develop query-efficient linearity test..