__
TR98-007 | 12th January 1998 00:00
__

#### Recycling Queries in PCPs and in Linearity Tests

**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^{-k}$. 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.

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 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.

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.