Tata Institute of Fundamental Research
Old and New PCP Constructions
STCS Faculty Seminar
Speaker:
Prahladh Harsha
Organiser:
Rahul Vaze
Date:
Tuesday, 17 Mar 2015, 16:00 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: The PCP theorem (AS,ALMSS 1991) guarantees that every NP language has a probabilistically checkable proof (PCP) system allowing a verifier to check a witness very efficiently using randomness, and allowing for small error.
Most of the talk will not assume prior knowledge, but I will also devote some time to some recent work joint with Dinur and Kindler.
In this work we make (some) progress towards proving the so-called "sliding-scale conjecture". This is a conjecture of Bellare-Goldreich-Lund-Russel from 1993 about the tradeoff between the number of bits read from the PCP proof and the error of the verifier. Our work revisits older constructions and analyzes them using the more modern "modular-composition" approach (based on joint work with Irit Dinur and Guy Kindler).
| Speaker: | Prahladh Harsha |
| Organiser: | Rahul Vaze |
| Date: | Tuesday, 17 Mar 2015, 16:00 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: The PCP theorem (AS,ALMSS 1991) guarantees that every NP language has a probabilistically checkable proof (PCP) system allowing a verifier to check a witness very efficiently using randomness, and allowing for small error.
Most of the talk will not assume prior knowledge, but I will also devote some time to some recent work joint with Dinur and Kindler.
In this work we make (some) progress towards proving the so-called "sliding-scale conjecture". This is a conjecture of Bellare-Goldreich-Lund-Russel from 1993 about the tradeoff between the number of bits read from the PCP proof and the error of the verifier. Our work revisits older constructions and analyzes them using the more modern "modular-composition" approach (based on joint work with Irit Dinur and Guy Kindler).
Most of the talk will not assume prior knowledge, but I will also devote some time to some recent work joint with Dinur and Kindler.
In this work we make (some) progress towards proving the so-called "sliding-scale conjecture". This is a conjecture of Bellare-Goldreich-Lund-Russel from 1993 about the tradeoff between the number of bits read from the PCP proof and the error of the verifier. Our work revisits older constructions and analyzes them using the more modern "modular-composition" approach (based on joint work with Irit Dinur and Guy Kindler).