Talks

1. The Communication Complexity of Correlation.
   • Long Version (1 hour)[ pdf (0.69MB) ]
     
2. Short PCPs verifiable in polylogarithmic time.
   • Long Version (1 hour) [ ppt (2.26MB) | ps (x6, 0.83MB) ]
     
3. 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!!
4. Robust PCPs of proximity, shorter PCPs and applications to coding.
   • Long Version (1 hour talk) [ ppt (2.56MB) | ps (x6, 1.10MB) ]
   • Short Version (STOC talk, 20 mins) [ ppt (1.63MB) | ps (x6, 0.54MB) ]
5. Some 3CNF properties are hard to test.
   • Short Version (STOC talk, 20 mins) [ ppt (0.75MB) | ps (x6, 0.42MB) ]
6. Small PCPs with low query complexity.
   • Short Version (STACS talk, 25 mins) [ ps (1.81MB) ]

Prahladh Harsha