Algebraic Graph Algorithms

Course description: This course covers algebraic and structural techniques for graph algorithms, including tree decompositions, polynomial identity testing, determinants and Pfaffians, matroids, matching, and fast matrix multiplication.

Textbooks:  There is no course text.

Prerequisites: Mathematical maturity and comfort with undergraduate algorithms, basic probability and linear algebra.

1. Lecture 1: Warm up (1) Algorithms on trees (8/1/2014), Scribe: Prafullkumar P Tale [pdf]

2. Lecture 2: Warm up (2) Algorithms on t-decomposible graphs (9/1/2014), Scribe: Anantha Padmanabha MS [pdf]

3. Lecture 3: Defining Tree Decompositions and their existence (10/1/2014), Scribe: Aditya Potukuchi [pdf]

4. Lecture 4: Another equivalent definition of Tree Decompositions (13/1/2014), Scribe: Diptapriyo Majumdar [pdf]

5. Lecture 5: An Approximation Algorithm for finding Tree Decomposition of a graph (14/1/2014), Scribe: Roohani Sharma [pdf]

6. Lecture 6: Nice Tree Decompositions and Dynamic Programming on them (15/1/2014), Scribe: Prafullkumar P Tale [pdf]

7. Lecture 7: Determinants, PIT and reducing Perfect Matching to PIT (20/1/2014), Scribe: Anantha Padmanabha MS [pdf]

8. Lecture 8: Finding weight of minimum weighted cycle in a graph (21/1/2014), Scribe: Aditya Potukuchi [pdf]

9. Lecture 9: Pfaffian of a Matrix (22/1/2014), Scribe: Diptapriyo Majumdar [pdf]

10. Lecture 10: Counting number of Perfect Matchings in a graph using Pfaffian orientation (27/1/2014), Scribe: Roohani Sharma [pdf]

11. Lecture 11: Finding Perfect Matching in O(n^(w+1)) time (28/1/2014), Scribe: Prafullkumar P Tale [pdf]

12. Lecture 12: Finding Perfect Matching in O(n^w) time (Hervey's Algorithm) (28/1/2014), Scribe: Anantha Padmanabha MS [pdf]

13. Lecture 13: Introduction to Matroids (1/2/2014), Scribe: Sanjukta Roy [pdf]

14. Lecture 14: Representability of Matroids, Reduction of graph problems to Matroid Intersection and Matroid Parity (1/2/2014), Scribe: Sanjukta Roy [pdf]

15. Lecture 15, 16: Solving Matroid Parity (3/2/2014, 5/2/2014), Scribe: Aditya Potukuchi [pdf]

16. Lecture 17, 18: An O(mr^w) Algorithm for Matroid Parity (12/3/2014, 17/3/2014), Scribe: Aditya Potukuchi [pdf]

17. Lecture 19: An O(m^w) algorithm for deciding Matroid Parity (19/3/2014), Scribe: Aditya Potukuchi [pdf]

18. Lecture 20: An O(mr^(w-1)) algorithm for Matrid Parity (24/3/2014), Scribe: Aditya Potukuchi [pdf]

19. Lecture 21: Matrix Multiplication and some applications (26/3/2014), Scribe: Diptapriyo Majumdar [pdf]

20. Lecture 22, 23: All pair Shortest Paths in O(n^w log n) time (5/4/2014), Scribe: Roohani Sharma [pdf]

21. Lecture 24: Finding the witness matrix in almost O(n^w) time (26/3/2014), Scribe: Sanjukta Roy [pdf]

22. Presentation 1: Lemma of Gessel Viennot (22/4/2014), Diptapriyo Majumdar [pdf]

23. Presentation 2: Proof of Tutte’s Matrix Tree Theorem using Gessel Viennot lemma (23/4/2014), Sanjukta Roy [pdf]

24. Presentation 3: Counting Steiner Trees and Hamiltonian Cycles on bounded treewidth graphs (25/4/2014), Aditya Potukuchi [pdf]

25. Presentation 4: Courcelle's Theorem (25/4/2014), Anantha Padmanabha MS [pdf]

26. Presentation 5: Solving Minimum Steiner Tree on bounded treewidth graphs using Guassian elimination (2/5/2014), Roohani Sharma [pdf]

27. Presentation 6: Construction of Almost k-wise Independent Random Variables (11/5/2014), Prafullkumar P Tale [pdf]