Luca Trevisan.<br>
<b>Recycling Queries in PCPs and in Linearity Tests</b><br>


<dl>

<dt> <b> Abstract</b> <dd>
We study query-efficient Probabilistically Checkable 
Proofs (PCPs) and linearity tests. We focus on the number 
of amortized query bits. A testing algorithm uses <i>q</i> amortized 
query bits if, for some constant <i>k</i>, it  reads <i>qk</i> bits and has 
error probability at most 2<sup><i>-k</i></sup>. 
The best known PCP construction 
for NP in this respect uses 3 amortized query bits (Hastad, STOC97); 
at least one amortized query bit is necessary, unless P=NP (Bellare, 
Goldreich and Sudan, FOCS95). This parameter is an extremely natural
one and has applications to proving non-approximability for
constraint satisfaction problems. Furthermore, a PCP  characterization
of NP with less than 2 amortized query bits would imply a separation
of the PCP model from the 2-Prover 1-Round  model.

<p>

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. 

<p>

We first apply this idea in order to develop query-efficient
linearity tests. Linearity testing is a problem closely related
to testing the Long Code and making PCP constructions. It  is also a
significant combinatorial problem still lacking tight characterizations,
except for the case of three queries (Bellare et al. FOCS95).
The best known linearity test uses 3 amortized query bits (Bellare
et al., FOCS95);  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 (Bellare, Goldreich and 
Sudan, FOCS95). We develop a general analysis technique and a linearity
test achieving simultaneously amortized query complexity 1.5 and 
amortized free bit complexity 1/2. This test answers an open question
raised by Bellare, Goldreich and Sudan.

<p>

We then show how to adapt a weaker result to the PCP setting, and we 
obtain a PCP for NP that makes 5 queries and has error probability 
1/4, so that its amortized query complexity is 2.5.