The Communication Complexity of Correlation.
Short PCPs verifiable in polylogarithmic time.
Communication vs. Computation.
- Short Version (ICALP talk, 30 mins) [ ppt (0.47MB) |
ps (x6, 0.22MB) ]
We are thankful to Piotr Indyk for presenting this talk
at ICALP '04 in our absence.
Yes, all the five authors could not attend the conference!!
Robust PCPs of proximity, shorter PCPs and applications to
Some 3CNF properties are hard to test.
Small PCPs with low query complexity.