CS 6550 - Advanced Algorithms

Fall 2010 - Tuesday/Thursday 12:00-13:30

School of Mathematical Sciences
Georgia Institute of Technology

Instructor: Asaf Shapira

Course procedures, syllabus and text books

Home Assignments

• Home Assignment I

• Home Assignment II

• Home Assignment III

• Home Assignment IV

Topics covered

Randomized Algorithms

• Lecture 1: Papadimitriou's random walk algorithm for 2-SAT.

• Lecture 2: Schoning's random walk algorithm for 3-SAT.

• Lecture 3: Second moment method (Chebyshev's Inequality), higher moment inequalities and Chernoff-type Inequalities.

• Lecture 4: Balls and bins, Birthday paradox, Maximum Load and Coupon collector. A 1/2-approximation algorithm for Max-Cut and its derandomization.

• Lecture 5: Contstructions of pairwise-independent random variables. Application to Universal hash functions.

• Lecture 6: Construction of Perfect Hash Tables (Fredman, Komlos and Szemeredi). Lower bound on size of pairwise indepedent sample spaces.

• Lecture 7: Construction of k-wise independent random variables using BCH codes. Lower bound on size of k-wise independent sample spaces.

• Lecture 8: The power of two choices.

• Lecture 9: Hardness of finding unique solutions (Valiant-Vazirani Theorem). Discrepancy of 4-wise independent indicators. Canteli-Chebyshev Inequality.

Fixed Parameter Algorithms

• Lecture 10: A 2-approximation for the vertex cover problem and a fixed parameter algorithm for it.

• Lecture 11: Fixed parameter algorithm for finding k-paths using Color-Coding (Alon-Yuster-Zwick). An O(logn)-approximation for the Feedback-Vertex-Set problem and a fixed parameter algorithm for it.

Combinatorial Approximation Algorithms

• Lecture 12: Analysis of the greedy approximation algorithms for Set-Cover and Maximum-Coverage.

• Lecture 13: A 3-approximation algorithm for Feedback-Vertex-Set. A 2-approximation algorithm for k-Center.

• Lecture 14: 2-Approximation for Steiner-Tree problem. 3/2-Approximation for metric TSP (Christofides's Algorithm).

• Lecture 15: O(logn)-Approximation for Asymmetric TSP (Frieze-Galbiati-Maffioli). O(log*n)-Approximation for Assymetric k-center problem (Panigrahy-Vishwanathan).

Maximum Matching

• Lecture 16: Schwartz-Zippel Lemma. Computing size of maximum matching in bipartite graphs.

• Lecture 17: Computing size of Maximum Matching in general graphs using Tutte's matrix (Lovasz). Augmenting paths (Berge's Theorem). Finding Maximum Matching and Minimum Vertex Cover in bipartite graphs. Konig-Egervary Theorem.

• Lecture 18: Maximum matching in bipartite graphs (Hopcroft-Karp Algorithm)

• Lecture 19: Maximum Matching in general graphs (Edmonds' Blossom-Shrinking Algorithm)

Fast Matrix Multiplication and Shortest Paths

• Lecture 20: Fast Matrix Multiplication (Strassen's Algorithm). Matrix multiplication and the All Pairs Shortest Paths Problem.

• Lecture 21: All Pairs Shortest Paths using Fast Matrix Multiplication (Seidel's Algorithm). Finding witnesses for Boolean Matrix Multiplication. Finding witnesses for APSP.

Eigenvalues and Expansion

• Lecture 22: Graph Laplacian. Relation between second eigenvalue and connectivity.

• Lecture 23: Relation between second eigenvalue and vertex connectivity (Fiedler). The "easy" direction of Cheeger's Inequality (Alon-Milman/Tanner). Second eigenvalue as a relaxation of Sparsest-Cut.

• Lecture 24: The "hard" direction of Cheeger's Inequality (Alon). The spectral partition algorithm for finding sparse cuts.

• Lecture 25: d-regular expanders and the expander mixing lemma (Alon/Chung).

• Lecture 26: Vertex expansion and Tanner's Theorem. Fast mixing of random walks on expanders.

• Lecture 27: Constructing Error-Correcting Codes from Expander Graphs

• Lecture 28: A Linear-Programming relaxation of Sparsest-Cut (Leighton-Rao). Rounding the LP using Metric Embedding (Linial-London-Rabinovich). An integrality gap instance using expanders.