51815 | Fall 2016 | T TH 11-12:30 | GDC 4.302
Instructor: Dana Moshkovitz
This class is about approximation algorithms and their limitations. It covers: combinatorial approximation algorithms; approximation algorithms based on linear and semidefinite programming; hierarchies of linear and semidefinite programming; limitations of the aforementioned techniques with connections to communication complexity and proof complexity; hardness of approximation and connections to multi-prover games and probabilistic checking of proofs; the proof of the PCP theorem, including combinatorial and algebraic techniques; sum-check; linearity testing; low degree testing; locally testable and decodable codes; composition; parallel repetition; long code, Fourier analysis and optimal inapproximability results; the Unique Games Conjecture; dictator tests and integrality gaps.
Format: Some of the meetings will be regular lectures, and some will be “workshops” in which the students give mini-lectures. Before each workshop there will be a schedule with the topics of the mini-lectures. Usually there will be problems to solve and a mini-lecture will present a solution, but sometimes mini-lectures will be surveys or discussions of open problems. Students should register to give mini-lectures after the release of each workshop schedule. Workshops will give students ample opportunity to give lectures and receive feedback. There are no exams or problem sets apart from workshop participation and presentation.
Prerequisites: undergraduate algorithms and complexity theory.
|
|
Date |
Topic |
|
1 |
Thursday, August
25 |
Overview;
basic combinatorial approximation algorithms: vertex cover, set cover, 3SAT |
|
2 |
Tuesday, August
30 |
Workshop on approximation
basics, including constraint satisfaction problems, label-cover, unique
label-cover |
|
3 |
Thursday,
September 1 |
Linear
programming (LP) and approximation algorithms |
|
4 |
Tuesday,
September 6 |
Self-study on LP and
limitations |
|
5 |
Thursday,
September 8 |
Self-study
on LP and limitations |
|
6 |
Tuesday, September
13, |
Workshop on approximation
algorithms based on linear programming |
|
7 |
Thursday, September
15, |
Semidefinite
programming (SDP), Max-Cut approximation |
|
8 |
Tuesday, September
20, |
Workshop on SDP and their
limitations |
|
9 |
Thursday, September
22 |
Hierarchies
of linear and semidefinite programming and their limitations |
|
10 |
Tuesday, September
27 |
Workshop on hierarchies,
connections to proof complexity and communication complexity |
|
11 |
Thursday,
September 29 |
Hardness
of Approximation, Multi-prover games and probabilistic checking of proofs
(PCP) |
|
12 |
Tuesday,
October 4 |
Workshop on PCP basics,
including expanders and randomness efficient sequential repetition,
transformation to two queries, degree reduction |
|
13 |
Thursday,
October 6 |
Self-study
on Linearity
testing |
|
14 |
Tuesday,
October 11 |
Self-study on Fourier
analysis |
|
15 |
Thursday,
October 13 |
Hadamard-based
PCP |
|
16 |
Tuesday,
October 18 |
Workshop on linearity
testing and quadratic testing, Fourier, locally testable and decodable codes |
|
17 |
Thursday,
October 20 |
Sum-Check
and PCP with polylog queries |
|
18 |
Tuesday,
October 25 |
Workshop on sum-check and
its many applications, low degree testing, |
|
19 |
Thursday,
October 27 |
Composition,
PCP of proximity, robust PCP, decoding PCP |
|
20 |
Tuesday,
November 1 |
Workshop on composition,
connection to code concatenation |
|
21 |
Thursday,
November 3 |
Gap
amplification (powering) |
|
22 |
Tuesday,
November 8 |
Workshop on gap
amplification and its limitations |
|
23 |
Thursday,
November 10 |
Parallel
repetition |
|
24 |
Tuesday,
November 15 |
Workshop on parallel
repetition, including lower bounds |
|
25 |
Thursday,
November 17 |
The
long code and optimal inapproximability results |
|
26 |
Tuesday,
November 22 |
Workshop on long code and
optimal inapprox |
|
Thursday,
November 24 |
Thanksgiving |
|
|
27 |
Tuesday,
November 29 |
The Unique Games Conjecture |
|
28 |
Thursday,
December 1 |
Dictator
tests and integrality gaps |