CSE 713 - Probabilistically Checkable Proofs and
Inapproximability
Fall 2004
Instructor: Dr. Hung Q. Ngo
Office: 239 Bell Hall
Office Hours: Thursdays 10:00-12:00
Phone: 645-3180 x 160
Email: hungngo@cse.buffalo.edu
Website: http://www.cse.buffalo.edu/~hungngo/SUBNET/seminars/PCP/
Grading: to be done on an S/N (or S/U) basis only.
Time and place: Mondays 3:30-5:00pm, and Wednesdays
3:30-5:00pm at Bell 242.
The first meeting is on Monday, Aug 30.
Description:
The PCP Theorem is one of the most important theorems in theoretical CS
of the past decade. The connection between interactive proof systems,
in particular probabilistically checkable proofs (PCP), and (tight)
inapproximability results for NP-optimization problems is another
important and relatively new discovery. Optimal or near-optimal
approximation ratios of many core NP-optimization problems have been
found using this connection: Max-3SAT, Max-Cut, Max-Clique,
Chromatic-Number, Vertex-Cover, etc.
In this seminar, I aim to outline main results concerning THE
connection between PCP and approximation algorithms. This should take
roughly half of the semester. The rest of the semester is for students'
presentations, where students read and presents papers filling out the
knowledge gaps I left (i.e. mention without proof).
Objectives:
- Have fun learning!
- Basic ideas and techniques of interactive proof systems.
- Basic ideas and applications of probabilistically checkable
proofs (PCP)
- Techniques of showing inapproximability results
Topics (tentative): I won't be able to
cover all of these. Students have to read pieces here and there.
- Approximation algorithms, approximation ratios
- Gap problems and inapproximability proofs
- Probabilistically checkable proofs
- The PCP connection (The FGLLS reduction)
- Inner and outer verifiers, recursive composition of proofs
- Showing inapproximability results for Max-Clique, Vertex-Cover,
Max-3SAT, Max-Cut, etc.
- The parallel repetition theorem
- The PCP theorem
Course Load:
- About 20 pages of dense reading per week (i.e. no bedtime
reading).
- Each student is expected to do a presentation at some point
during the semester, based on:
- A survey done by the student on a particular topic to be
suggested by the instructor or picked by the student but approved by
the instructor.
- A (few) very dense mathematical paper.
- An open problem solved by the student.
Prerequisites:
- Find learning new things fun.
- Find learning mathematics fun.
- Find solving mathematical puzzles fun.
- Find the instructor funny.
- OK, the real deals are: rudimentary knowledge on linear algebra,
algorithms, probability theory, complexity classes. They are not
entirely essential to follow things presented in the seminars. Related
background materials shall be provided in the forms of small
tutorials/notes. You'd have to read them though.