Lecture 1  January 3, 2019 
A sample of approximation algorithms
* 2approximation algorithm for Vertex Cover in polynomial time * 1.99approximation algorithm for Vertex Cover in time 1.1^{n} 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 mincut 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/8fraction of clauses in a 3CNF formula 
Lecture 4  January 15, 2019 
Satisfying 7/8fraction of clauses in a 3CNF 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.
2approximation for metric TSP. Christofides' algorithm: 1.5approximation for metric TSP. log(n)approximation for asymmetric TSP. 
Lecture 8  January 29, 2019 
Polynomial identity testing: the SchwartzZippel 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.
FourierMotzkin elimination. Basic feasible solution. 
Lecture 11  February 7, 2019 
BeckFiala theorem.
Duality in linear programming. 
Lecture 12  February 14, 2019 
The weighted vertex cover problem

Lecture 13  February 26, 2019 
Semidefinite programming
0.878approximation algorithm for maxcut (GoemansWilliamson) 
Lecture 14  February 28, 2019 
Coloring 3colorable graphs
Wigderson's algorithm SDP based algorithm (Karger, Motwani, Sudan) 
Lecture 15  March 5, 2019 
Coloring 3colorable 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 BeckFiala 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 