Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Carsten Lund:

TR98-008 | 15th January 1998
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

Proof verification and the hardness of approximation problems.

We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
<em> constant </em> number of bits in the proof.
If a string is in the language, then there exists a proof ... more >>>

ISSN 1433-8092 | Imprint