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