| Lecture 1 - January 3, 2019 |
A sample of approximation algorithms
* 2-approximation algorithm for Vertex Cover in polynomial time * 1.99-approximation algorithm for Vertex Cover in time 1.1n A sample of randomized algorithms * Computing the area of a unit circle * Freivalds' algorithm for verifying matrix multiplication |
| Lecture 2 - January 8, 2019 |
Karger's min-cut algorithm
Communication complexity: checking equality of two strings Random matrices generate good codes. |
| Lecture 3 - January 10, 2019 |
Some basic probability facts
* Linearity of expectation * Concentration inequalities Satisfying 7/8-fraction of clauses in a 3-CNF formula |
| Lecture 4 - January 15, 2019 |
Satisfying 7/8-fraction of clauses in a 3-CNF formula deterministically
Discrepancy using Chernoff bound ln(n)-approximation for Set Cover |
| Lecture 5 - January 17, 2019 |
Algorithms for approximating the clique problem
|
| Lecture 6 - January 22, 2019 |
Solving Hamiltonian path using a dynamic algorithm.
Finding a path of length O(log(n)) using color coding. |
| Lecture 7 - January 24, 2019 |
The traveling salesman person problem.
2-approximation for metric TSP. Christofides' algorithm: 1.5-approximation for metric TSP. log(n)-approximation for asymmetric TSP. |
| Lecture 8 - January 29, 2019 |
Polynomial identity testing: the Schwartz--Zippel lemma
Finding a perfect matching in a bipartite graph |
| Lectures 9 - January 31, 2019 |
Finding a minimum weight perfect matching in a bipartite graph
|
| Lecture 10 - February 5, 2019 |
Linear Programming: simple examples.
Fourier-Motzkin elimination. Basic feasible solution. |
| Lecture 11 - February 7, 2019 |
Beck-Fiala theorem.
Duality in linear programming. |
| Lecture 12 - February 14, 2019 |
The weighted vertex cover problem
|
| Lecture 13 - February 26, 2019 |
Semidefinite programming
0.878-approximation algorithm for max-cut (Goemans-Williamson) |
| Lecture 14 - February 28, 2019 |
Coloring 3-colorable graphs
Wigderson's algorithm SDP based algorithm (Karger, Motwani, Sudan) |
| Lecture 15 - March 5, 2019 |
Coloring 3-colorable graphs using SDP (cont.)
Property testing: first example |
| Lecture 16 - March 12, 2019 |
Linearity testing
Fourier analysis of Boolean functions |
| Lecture 17 - March 14, 2019 |
The PCP Theorem and hardness of approximation
|
| Lecture 18 - March 19, 2019 |
Hardness of approximation for clique using the FGLSS reduction
|
| Due to Thursday, February 7, 2019 |
Assignment 1
|
| Due to Thursday, March 7, 2019 |
Assignment 2
|
| Due to Thursday, March 28, 2019 |
Assignment 3
|
| March 26, 2019 |
Speaker: Anurag Sanyal
Approximating Maximum Clique by Removing Subgraphs Speaker: Amirhosein Kazeminia Testing triangle freeness in dense graphs |
| March 28, 2019 |
Speaker: Fatemeh Hasiri
Finding Hidden Cliques in Linear Time with High Probability Speaker: Mona Mehdizadeh Sublinear Algorithms for (Δ+1) Vertex Coloring |
| April 2, 2019 |
Speaker: Akbar Rafiey
On the Beck-Fiala Conjecture for Random Set Systems Speaker: Zhenjian Lu On Khot's unique games conjecture |
| April 4, 2019 |
Speaker: Neda Shokraneh
Unique Games on Expanding Constraint Graphs are Easy Speaker: Sophie Oh Expander Flows, Geometric Embeddings and Graph Partitioning |