## Lecture 2: The two views of PCP

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

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

## Lecture 1: Introduction

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.

## Presentations

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).

leave a comment