| Lecturer |
He Sun
|
|
| Date: |
March 3-14, and March 24-28, 2014 |
| Place: |
Rotunda of the 3rd floor, Campus E1. 4 |
| Time: |
2-4pm, everyday |
| Notice |
This Doctoral Privatissima is a block course for three weeks. For more information about Doctoral Privatissima, click
HERE.
|
| Credits | You earn 6 Credit Points (LP). |
| Grading | Students who register the course need to read one paper from the list below, and give an about 2-hour
presentation with detailed analysis. |
| Prerequisites |
Basic knowledge of algorithm design and linear algebra. |
| Content |
Spectral Graph Theory studies the matrix representations of graphs, and offers many unexpected and beautiful connections between two apparently
unrelated branches of mathematics: Algebra and Graph Theory. Due to this connection,
various algebraic questions can be reduced to graph problems, and this insights lead to some new techniques in designing graph algorithms.
|
| Topics |
- Graphs and Groups.
- Matrix Theory.
- Cheeger's Inequality.
- Paths, Flows, and Routing.
- Explicit Constructions of Expanders.
- Spectral Graph Theory on Subgraphs.
|
| Schedule |
| Date |
Topic |
References |
| March 4
|
Eigenvalues and the Laplacian of a graph
|
Chapter 1 of Ref. 1
|
| March 5
|
Isoperimetric problems
|
Chapter 2 of Ref. 1
|
| March 6
|
Path, flows, and routing
|
Chapter 4 of Ref. 1
|
| March 10
|
Eigenvalues and quasi-randomness
|
Chapter 5 of Ref. 1
|
| March 11
|
Expanders and explicit constructions
|
Chapter 6 of Ref. 1, Ref. 2, and My Old Notes
|
| March 12
|
Eigenvalues of Symmetric Graphs
|
Chapter 7
|
| March 13
|
Eigenvalues of subgraphs with boundary conditions
|
Chapter 8
|
|
| Papers for Presentation |
- Shayan Oveis Gharan, Luca Trevisan: A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM 2013: 303-316.
- James R. Lee, Shayan Oveis Gharan, Luca Trevisan: Multi-way Spectral Partitioning and Higher-order Cheeger Inequalities. STOC 2012: 1117-1130.
- Adam Marcus, Daniel Spielman, and Nikhil Srivastava: Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem, 2013.
- Daniel Spielman, and Nikhil Srivastava: Graph Sparsification by Effective Resistances, SIAM Journal on Computing, 40(6), pages 1913-1926, 2011.
- Anastasios Zouzias: A Matrix Hyperbolic Cosine Algorithm and Applications. ICALP (1) 2012: 846-858.
|
| Similar Courses |
|
| Main References |
- [1] Fan Chung: Spectral Graph Theory, American Mathematical Society, 1997. First four chapters can be downloaded via the link.
- [2] Omer Reingold, Salil Vadhan and Avi Wigderson. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Annals of Maths. 155:157-187, 2002.
|
