Expanders, Property Testing and the PCP theorem

Lecture 2: The two views of PCP

Posted in lectures by atri on August 29, 2008

In today’s lecture, we saw more on the prover-verifier view of the PCPs and approximation algorithms. We also briefly heard some hand-wavy reasons why we should expects codes to prop up in the proof of the PCP theorem.

Next lecture, Hung will connect these two “disparate” view and give an overview of the main steps in Dinur’s proof.

Change in meeting times

Posted in annoucements by atri on August 29, 2008

We will now meet 10:30am-noon on Mondays and Fridays in Bell 224.

Lecture 1: Introduction

Posted in lectures by atri on August 28, 2008

In today’s lecture, we saw two “disparate” interpretations of languages in NP: in particular, the proof-verifier definition of NP (and PCPs) and approximation algorithms for NP-complete problems (3ESAT in particular). We also saw the statement of the wonderful and mysterious PCP theorem.

Next lecture, we will wrap up some left over discussion about these two views and then go on to show that the views are actually the same.

Today’s lecture was based on these lecture notes.

Also in class I mentioned that the PCP theorem has an very interesting history. For a very nice description, see this writeup by Ryan O’Donnell.


Posted in presentations by atri on August 28, 2008

You will present papers in pairs. Each pair will get two weeks to present two papers: one on expanders and one on property testing. Email us your pair’s information by Wednesday, September 3, 2008. The student presentations on papers related to expanders will start in about 4.5 weeks.

Some suggestions for papers related to expanders is already online. The list of suggested papers on property testing should be up in a a couple of weeks at the same place. You can choose a paper outside the list, which is relevant (get approval from us first though).

Please let us know as soon as your group chooses a paper (as the ones in the suggested list will be “alloted” on a first-come-first-serve basis).