Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sum-check:
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