18.434 Seminar in Theoretical Computer Science

Fall 2011

This site can be accessed at http://www-math.mit.edu/~goemans/18434.html and will be continuously (actually, discretely) updated.

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