Course info:
|
|
Class: |
MW 3:25-4:40pm,
Lechase Room 181 |
Instructor: |
Kaave Hosseini
Email:
kaave.hosseini (rochester.edu) |
Office hours: |
W 4:50-6:00pm, Wegmans 2507 |
Lecture notes & Homework:
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. |
| Some of the questions that we discuss are: |
Unsupervised learning: Cluster some given unlabeled data to two or more similar clusters. How can we cluster data when dimension is too high? or when some common techniques like k-means break down? |
Supervised learning: Which concept classes are learnable? How can we learn an unknown concept with a few samples?
|
Coding theory: How can we transmit or store data in a noisy(possibly adversarial) environment in a way that can be correctly recovered? |
Social choice theory: Which election system is most stable with respect to noise? Can we always have a fair and meaningful election system? |
Expanders: How can we build the most reliable network with the fewest number of connections?
|
Property testing: Given a big amount of data (say a big graph), which properties of the graph can be decided based on constantly many samples?
|
Derandomization: Is randomness necessary to solve problems or we can get away with deterministic algorithms?
|
Ramsey theory: How can we explicitly build Ramsey graphs?
|
Hardness of approximation: Which NP-complete problems are hard to even reach an approximate solution?
|
Markov Chains: How fast does a Markov Chain converge to its stationary distribution?
|
Number theory: Given an arbitrary (dense) subset of integers, is there always a nice pattern in it?
|
Dimensionality reduction: Can we significantly reduce the dimension of data without losing critical information?
|
Topics and Resources:
Here are some suggested resources.
Linear algebra background
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapters 1 provides the linear algebra background. |
Basics of spectral graph theory, Laplacian, etc.
| Lecture notes on Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan. Chapters 2 and 3. |
| 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. |
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. |
| Book draft on Spectral and Algebraic Graph Theory by Dan Spielman. |
Application in spectral clustering and image segmentation
| Lecture notes On spectral clustering and Power method by Oveis Gharan |
| Paper on spectral clustering A. Ng, M. Jordan, and Y. Weiss. |
| 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
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. |
