Course info:
Course syllabus |
|
Class: |
MW 4:50-6:05pm, Dewey 2110D |
Instructor: |
Kaave Hosseini Email: kaave.hosseini (rochester.edu) |
Office hours: |
Wed 2:00-3:15 pm Wegmans 2507 |
Lecture notes & Homework:
| on Piazza. |
Course plan:
| The purpose of this course is two-fold. First is to introduce spectral techniques as a powerful tool to solve problems in different areas. Second is to give an introduction to a variety of areas and show how spectral methods can be applied to fundamental problems in each area. The areas covered are Clustering, Approximation algorithms, error-correcting codes, randomized algorithms, derandomization, program/property testing, Probabilistically checkable proofs, Social choice theory, PAC learning, pseudorandomness, Hardness of approximation, and additive combinatorics. |
Topics and Resources:
Here are some suggested resources.
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapters 1 and 2 provide the linear algebra background and a broad overview of spectral graph theory. |
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapters 1 provides an introduction and also some interesting concrete examples about the eigenvalues of graphs and drawings based on eigenvectors of graphs. |
| Book on Extremal Combinatorics by Jukna. Some sections in part III of this book provide basics of SGT and many other related techniques that are broadly based on linear algebra. |
| Book on Spectral graph theory by Fan Chung. An introduction to Laplacian treating the general cases of arbitrary degree graphs and weighted graphs. Also gives analysis of random walks on weighted graphs. |
Computing eigenvalues and eigenvectors
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Section 9.3 introduces The Power Method to approximate eigen values of graphs. |
Application in graph drawing
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapter 1 provides some interesting examples of drawings of graphs based on eigenvalues. Sections 3.2 explains Hall's approach to draw graphs based on eigenvalues. |
| Paper on spectral graph drawing by Yehuda Koren |
Cheeger's inequality
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapter 4 provides proof of Cheeger's inequality for regular graphs. Higher order analogues of Cheeger's inequality are discussed in chapters 7-8. |
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapter 21 provides proof of Cheeger's inequality for arbitrary degree graphs. |
| Book on Spectral graph theory by Fan Chung. Chapter 2 dicusses Cheeger's inequality as an isoperimetric inequality and gives a different proof in the the general setting. |
Better approximation algorithms for the sparsest cut problem
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapters 10-15 discuss the Sparsest Cut Problem. Algorithms based on linear programming and semidefinite programming are introduced. |
Application in spectral clustering and image segmentation
| Paper on spectral clustering algorithms by U. von Luxburg. Gives a survey of spectral clustering algorithms. |
| Paper Normalized Cuts and Image Segmentation by J. Shi and J. Malik. Applies Cheeger inequality to the problem of image segmentation |
| Paper on clustering and image segmentation by D. Tolliver and G. Miller. |
Expanders
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapter 17-22 discuss expanders and their applications and constructions |
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapters 27-31 discusses expanders and the applications that we discussed in class. |
| Survey on Expanders and their applications by Hoory, Linal, and Wigderson. Survey paper discussing various constructions of expanders and their applications in coding theory, metric embedding, geometry, circuit complexity, etc. |
| Survey on expander graphs by Alex Lubotzky. A more geoemtric approach to expanders and applications to group theory and number theory. |
| Paper by Bilu and Linial on an inverse to expander mixing lemma. This paper gives an inverse to expander mixing lemma, roughly speaking shows that if a graph has low discrepancy, then its second-larges eigenvalue is small. |
| Survery on Ramanujan graphs. |
Application in error correcting codes
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapter 29 gives a construction of expander codes similar to the one given in class. |
| Book on Extremal Combinatorics by Jukna. |
| Lecture note by M. Sudan. |
| Lecture note by Venkat Guruswami. A more in-depth look at expander codes. |
Application in error reduction of algorithms
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Chapter 31 gives application of random walks on expanders in error reduction. |
| Book on Extremal Combinatorics by Jukna. |
| Book chapter by Salil Vadhan. |
Expander Chernoff bound
| Book chapter by Salil Vadhan. Theorem 4.22 is Chernoff bound for random walks on expanders. |
Construction of expanders
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. Construction based on line graph in chapter 30. |
| Book chapter by Salil Vadhan. Gives a broad overview of different constructions. |
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapters 17-20 are about constructions. First zig-zag product construction is introduced and then the algebraic construction of Margulis-Gabber-Galil is explained in chapter 19. Chapter 20 discusses probabilistic construction as done in class. |
| Survey on Expanders and their applications by Hoory, Linal, and Wigderson. |
Basics of Fourier analysis
| Lecture notes on analysis of boolean functions by Ryan O'Donnell |
| Book on analysis of boolean functions by Ryan O'Donnell. A reference book with a lot of material. We will cover chapters 1,2,3,9. |
| Lecture notes on analysis of boolean functions by Tom Sanders. |
| Lecture notes on Fourier analysis of boolean functions by Shachar Lovett. |
Application in linearity testing
| Lecture notes on analysis of boolean functions by Ryan O'Donnell. |
| Book on analysis of boolean functions by Ryan O'Donnell. Section 1.6. |
| Lecture notes on Fourier analysis of boolean functions by Shachar Lovett. |
Application of linearity testing in coding theory and PCP constructions
| Lecture note by Prahladh Harsha. |
| Lecture note by Jose Falcon, Mitesh Jain on PCP theorem. |
Application in social choice
| Lecture notes on analysis of boolean functions by Ryan O'Donnell. |
| Lecture notes on Fourier analysis of boolean function by Shachar Lovett. |
| Book on analysis of boolean functions by O'Donnell. |
Application in learning theory
| Book on analysis of boolean functions by O'Donnell |
| Lecture notes on analysis of boolean functions by O'Donnell |
| Lecture notes on Fourier analysis of boolean function by Lovett. |
Small bias spaces and their constructions
| Lecture notes on Fourier analysis of boolean function by Lovett. |
| Lecture notes on small biased sets by Viola. . |
| Paper on an almost optimal construction of small biased sets by Ta-Shma. |
| Original Paper on construction of small biased sets by Naor and Naor. |
Application in coding theory
| Paper on an almost optimal construction of small biased sets and consequently balanced codes by Ta-Shma. |
Application in Combinatorics
| Lecture notes on epsilon-biased sets and application of almost k-wise independece in construction of Ramsey graphs and k-universal sets. |
Application in derandomization
| Original Paper by Alon et al. on construction of almost k-wise independence. |
Application of small bias in Roth's theorem
| Survey on additive combinatorics and its applications in theoretical computer science by Shachar Lovett. |
Application of small bias in (Hardness of) Approximation
| Lecture note by Holger Dell and Dieter van Melkebeek. |
Basics of additive combinatorics
| Survey on additive combinatorics and its applications in theoretical computer science by Shachar Lovett. |
Hypercontractivity and KKL theorem (Lecture by Arian Nadjimzadeh)
| Book on analysis of boolean functions by O'Donnell |
| Lecture notes on analysis of boolean functions by O'Donnell |
| Lecture notes on Fourier analysis of boolean function by Lovett. |
| Book on applications of noise sensitivity in Percolation theory by Christophe Garban and Jeffrey E. Steif. |
Regularity lemma and its applications (Lecture by Mandar Juvekar)
| Book chapter on Regularity lemma and its applications by Yufei Zhao. |
the great wave off Kanagawa, Hokusai, 1831.