| Week | Speaker | Topic |
|---|---|---|
| Aug 30 | Hung Q. Ngo | Approximation algorithms, approximation ratios, gap problems |
| Sep 06 | Hung Q. Ngo | PCP and the long code |
| Sep 13 |
Hung Q. Ngo | Folding of functions, recursive construction of proofs |
| Sep 20 |
Hung Q. Ngo | Atomic tests |
| Sep 27 | Hung Q. Ngo | Inner verifiers for Max-SNP problems |
| Oct 04 |
Hung Q. Ngo | Free bits and the FGLSS reduction |
| Oct 11 |
Hung Q. Ngo | Hastad's verifier and good inapproximability results for Max-3SAT, Max-Clique, Vertex Cover, Label Cover, MMAS |
| Oct 18 | Hung Q. Ngo |
Fourier Analysis |
| Oct 25 | Hung Q. Ngo |
Some optimal inapproximability results for Max-E3SAT, Max-Clique, Vertex-Cover |
| Nov 01 |
Hung Q. Ngo |
Amortized free bit complexity and Max-Clique |
| Nov 08 | Hung Q. Ngo | Hastad's verifier to prove hardness of Max-Clique |
| Nov 15 | Dazhen Pan | Raz' Parallel Repetition Theorem |
| Nov 22 |
Duc Ha | On the power of MIP |
| Nov 29 | Mingen Lin | On Weighted vs Unweighted Versions of Combinatorial Optimization Problems |
| Dec 06 | Jaikanth Krishnaswamy | A Threshold of ln n for Approximating Set Cover |