## Course Announcement: PCPs, codes and
inapproximability - Fall 2007

### PCPs, error-correcting codes and inapproximability results

Time: Tues/Thurs 2:30-4:00pm (tentative)

Location: Ryerson 276 (tentative)

Organizer :

Homepage:
http://ttic.uchicago.edu/~prahladh/teaching/fall07/

# PCPs, error-correcting codes and inapproximability results

The PCP theorem [AS, ALMSS] states the remarkable fact that any
mathematical proof can be written in a manner such that the validity
of the proof can be verified probabilistically by querying the proof
only at a constant number of locations. Following the proof of this
celebrated theorem and the connection between probabilistically
checkable proofs (PCPs) and hardness of approximation [FGLSS] (both
proved in the early 90's), this theorem was extremely powerful in
proving the NP-hardness of the approximate version of several
combinatorial optimization problems.

However, the early proofs of this theorem were extremely involved
and very "algebraic" in nature. Recently (2005), Irit Dinur gave a
remarkably simple, self-contained and "combinatorial" proof of the PCP
Theorem.

In this course, we will present Dinur's proof of the PCP Theorem, a
few applications of PCPs towards inapproximability results and coding
theory, improved PCP constructions (short and efficient PCPs)
etc. Topics covered will include a mixture of earlier and very recent
work, such as:

- Dinur's Proof of PCP Theorem
- Linearity testing, low degree testing
- Raz's Parallel Repetition Theorem
- Inapproximability results: linear equations, lattice problems
- PCP construction variants -- short PCPs, efficient PCPs etc.
- Applications toward coding: locally testable codes