When and where: MWF 1-2PM in 2-136.
Instructor: Michel Goemans, room 2-351.
Office hours: TBD. You'll be able to book appointments through a gmail calendar.
This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department.
The topic for this Spring is on Algebraic and Spectral Graph Theory and Applications. There are many problems on graphs that can be tackled using eigenvalues and algebraic approaches. Topics to be studied include electrical networks, random walks, properties of the Laplacian (counting trees, etc.), rubber bands and connectivity, eigenvalues for special classes of graphs, spectral graph partitioning, Cheeger's inequality, eigenvalue bounds for combinatorial optimization problems, graph sparsification, web search (PageRank, Hubs and Authorities), expander graphs, etc.
Support Material. The material covered will come from various sources. A very preliminary and incomplete list includes:
Students will be expected to present three times during the term. The goal of the presentations is to communicate effectively the material to the other students in the class. Each student will prepare a summary (between 1/2 page and one page) of his/her lecture. Each student will also be responsible for carefully writing lecture notes based on someone else's presentation. There will be some homework as well, and solutions will need to be typeset.
Grading policy. Your grade will be based on your presentations, your participation in class (during other presentations), on your lecture notes and on homework (both content and exposition).
Homework: TBD
Schedule:
date | presenter | topic | |
---|---|---|---|
Wed Sept 7 | M. Goemans | Intro | |
Fri Sept 9 | M. Goemans | ||
Mon Sept 12 | M. Goemans | ||
Wed Sept 14 | Bryan Rosario | Interpretation of voltages and current in an electrical network in terms of random walks. Summary. | |
Fri Sept 16 | Bryan (cont'd) and Sam Wong | Energy and Rayleigh's monotonicity principle | |
Mon Sept 19 | Sam Wong | Energy and Rayleigh's monotonicity principle. Summary. | |
Wed Sept 21 | Holiday - No class | ||
Fri Sept 23 | Rachel Chasin | Random spanning trees and electrical networks. Summary. | |
Mon Sept 26 | Katie Kauffman | Polya's theorem | |
Wed Sept 28 | Tim Kaler | Polya's theorem for 3D lattices | |
Fri Sept 30 | Mark Chen | Laplacian | |
Mon Oct 3rd | Michel Goemans | Laplacian and PSD (cont'd) | |
Mon Oct 3rd, 7:30PM | Jin Hao Wan | Laplacian - examples | |
Wed Oct 5th | Evelyn Cordner | Eigenvalue bounds for graph coloring + Courant-Fischer | |
Fri Oct 7th | Maddie Mirzoeff | Electrical networks and the Laplacian | |
Mon Oct 10th | Holiday -- No class | ||
Wed Oct 12th | Aizana Turmukhametova | Counting spanning trees | |
Fri Oct 14th | Aizana (cont'd) + Umaimah Khan | Partitioning - Cheeger's inequality | |
Mon Oct 17th | Umaimah Khan | Partitioning - Cheeger's inequality | |
Mon Oct 17th, 7:30PM | Umaimah (cont'd) + Ashwin Suresh | Expanders | |
Wed Oct 19th | Ashwin Suresh | Expanders + derandomization | |
Fri Oct 21th | No class (make-up on Oct 7th) | ||
Mon Oct 24th | Alex Dehnert | Maximum Cut problem | |
Wed Oct 26th | Alex Dehnert | Maximum Cut problem | |
Fri Oct 28th | Alex + Michel Goemans | Maximum Cut problem + demos | |
Mon Oct 31st | Ashwin Suresh | Expanders + derandomization (cont'd) | |
Wed Nov 2nd | Evelyn Cordner | Hubs and authorities | |
Fri Nov 4th | Mark Chen | Planar graphs: Koebe's theorem and 2nd eigenvalue | |
Mon Nov 7th | Mark Chen | ||
Mon Nov 7th, 7:30PM | Aizana Turmukhametova | Expander codes | |
Wed Nov 9th | Aizana Turmukhametova | ||
Fri Nov 11th | Veteran's day - no class | ||
Mon Nov 14th | No class (make-up on Oct 17th) | ||
Wed Nov 16th | No class (make-up on Nov 7th) | ||
Fri Nov 18th | No class (make-up on Dec 5th) | ||
Mon Nov 21st | Sam Wong | How to draw a planar graph? | |
Wed Nov 23rd | Sam Wong | Tutte's rubber band method for drawing planar graphs | |
Fri Nov 25th | Thanksgiving holiday - no class | ||
Mon Nov 28th | Rachel Chasin | Image processing | |
Wed Nov 30th | Bryan Rosario | Squaring the square using resistive networks | |
Fri Dec 2nd | Tim Kaler | Combinatorics of effective resistances and resistive inverses | |
Mon Dec 5th | Katie Kauffman | Spectral algorithms, Chap 1 | |
Mon Dec 5th, 7:30PM | Maddie Mirzoeff | ||
Wed Dec 7th | Jin Hao Wan | Graph sparsification by effective resistances | |
Fri Dec 9th | Ashwin Suresh | Better graph sparsifiers | |
Mon Dec 12th | |||
Wed Dec 14th |