MCS 590: Spectral Graph Theory (Spring 2020)
Basic Information
Instructor: Yu Cheng
Email: yucheng2@uic.edu
Lectures: M-W-F 1:00-1:50pm, Lincoln Hall 207
Office Hours: by appointment only
Schedule
- Week 1 (Jan 13): Graph Laplacians
- Introduction to the course
- Graph Laplacians, quadratic forms, eigenvalues
- Laplacian linear systems, spring and resistor networks
- Week 2 (Jan 20): Cheeger's Inequality
- Conductance, the normalized Laplacian, Cheeger's Inequality
- Spectral similarity, iterative solvers, preconditioning
- Week 3 (Jan 27): Solving Linear Systems
- Richardson iteration, Chebyshev polynomials
- Power method for approximating eigenvalues
- Gaussian elimination, nested dissection, planar separator theorem
- Week 4 (Feb 3): Effective resistance
- Schur complement of Laplacians, effective resistance
- Random walks, escape probabilities
- Monotonicity of effective resistance, commute times
- Week 5-6 (Feb 10): Graph sparsification
- Graph sparsification by effective resistances
- Linear-sized (Twice-Ramanujan) sparsifiers
- Linear-sized spectral sparsification in nearly-linear time
- Week 7-8 (Feb 24): Laplacian solvers
- Preconditioning by low-stretch spanning trees
- Approaching optimality for solving SDD linear systems
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- An efficient parallel solver for SDD linear systems
- Week 9 (Mar 9): Maximum flow
- Sparse Newton's method
- An almost-linear-time algorithm for approximate max flow in undirected graphs
- Week 10-11 (Mar 16): No classes. Spring break.
- Week 12 (Mar 30): Oblivious routing and maximum flow
- Oblivious routing: optimal hierarchical decompositions for congestion minimization in networks
- Approximating undirected maximum flow in nearly-linear time
- Week 13 (Apr 6): Sparsest cut
- Cut-matching games
- Partitioning graphs via single commodity flows
- Week 14-15 (Apr 13): Solving packing SDPs
- The multiplicative weights update method
- Faster and simpler width-independent parallel algorithms for positive semidefinite programming
- Faster algorithms for high-dimensional robust statistics
- Week 16 (Apr 27): Sketching cuts
- Expander partitioning
- Sketching quadratic forms
- Sketching cuts for directed graphs
Grading
Participation (50%): Each student will be assigned 2-3 papers to read and to present in class.
Course project (50%): Students will form groups of size 1-2 to work on research open problems. Write a project report and prepare a presentation.
Disability Policies
Concerning disabled students, the University of Illinois at Chicago is committed to maintaining a barrier-free environment so that individuals with disabilities can fully access programs, courses, services, and activities at UIC. Students with disabilities who require accommodations for full access and participation in UIC Programs must be registered with the Disability Resource Center (DRC). Please contact DRC at (312) 413-2183 (voice) or (312) 413-0123 (TDD).
Religious Holidays
Students who wish to observe their religious holidays shall notify the faculty member by the tenth day of the semester of the date when they will be absent unless the religious holiday is observed on or before the tenth day of the semester. In such cases, the students shall notify the faculty member at least five days in advance of the date when he/she will be absent. The faculty member shall make every reasonable effort to honor the request.