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



REPORTS > AUTHORS > YAEL TAUMAN KALAI:
All reports by Author Yael Tauman Kalai:

TR07-031 | 26th March 2007
Yael Tauman Kalai, Ran Raz

Interactive PCP

An interactive-PCP (say, for the membership $x \in L$) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages $L$, there are interactive-PCPs that are significantly shorter than the known ... more >>>



ISSN 1433-8092 | Imprint