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



REPORTS > AUTHORS > DANIEL LEWIN AND MADHU SUDAN:
All reports by Author Daniel Lewin and Madhu Sudan:

TR98-034 | 23rd June 1998
Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

A tight characterization of NP with 3 query PCPs

It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a {\em one-sided} error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-trivial verification power ... more >>>



ISSN 1433-8092 | Imprint