CSC/MATH 488/288 Analytic methods in computer science - Fall 2022

Course info:

Course syllabus
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:

are 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.
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

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.


image
the great wave off Kanagawa, Hokusai, 1831.