ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > LINEARITY TEST.:
Reports tagged with Linearity Test.:
TR98-007 | 12th January 1998
Luca Trevisan

Recycling Queries in PCPs and in Linearity Tests

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



ISSN 1433-8092 | Imprint