|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.
Basic feasible solution.
|Lecture 11 - February 7, 2019||
Duality in linear programming.
|Lecture 12 - February 14, 2019||
The weighted vertex cover problem
|Lecture 13 - February 26, 2019||
0.878-approximation algorithm for max-cut (Goemans-Williamson)
|Lecture 14 - February 28, 2019||
Coloring 3-colorable graphs
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||
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||
|Due to Thursday, March 7, 2019||
|Due to Thursday, March 28, 2019||
|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