The goal of this graduate topics course is to take students from the rudiments all the way
to some parts of the research frontiers of expansion, coding theory, and optimization both
from a classical and quantum perspective.
Main Topics
Expansion: Expander graphs combine two opposing properties of being well-connected yet
sparse. This powerful combination leads to a variety of applications in CS (and mathematics)
such as error correction, hardness of approximation, fast algorithms, sampling, etc. Recently, several notions
of high-dimensional expansion appeared, leading to exciting discoveries.
Coding theory: Codes are "robust" collections of strings that not only have implications
for protection against errors in communication and storage, but they also have connections
to diverse fields such as complexity theory, expansion, etc. Recently, many breakthrough
constructions of codes were discovered, such as explicit binary codes close to the GV bound,
good LTCs, and good qLDPC.
Optimization: Convex programming, in particular, linear programming (LP) and semi-definite programming (SDP),
are at the heart of many efficient algorithms. The use of powerful SDP hierarchies such as the Sum-of-Squares
hierarchy has recently found many algorithmic applications.
Course Phases
Phase 1
In this initial phase, we will cover some foundational topics of these fields which may include some of the following:
Expanders: Notions of expansion, Random Walks, Cheeger's inequality, Cayley graphs of Abelian groups, Zig-zag construction, Ramanujan Graphs
Coding Theory: Reed Solomon, Reed Muller, Hadamard, LDPC, Tanner, and Quantum CSS Codes, Operations: code concatenation, AEL, tensor, Some code bounds: GV bound, MRRW, Singleton, etc, List Decoding
Optimization: Linear programming (Delsarte's LP combining codes, Fourier analysis and LPs), Semi-definite programming, and Sum-of-Squares (CSPs on Expanders and a local-to-global phenomenon)
Spectral graph theory: Sensitivity Conjecture (signing, interlacing, etc), Johnson scheme (a complete analog of simplicial HDXs)
Phase 2
In this second phase, we will cover some recent topics at the research frontiers which may include some of the following:
Dinur's PCP by gap amplification
Explicit balanced codes close to the GV bound by Ta-Shma
Locally Testable Codes, Left-Right Cayley Complexes, c^3-LTC of Dinur et al
Good quantum LDPC Codes, Quantum Tanner Codes
Locally Decodable Codes, Matching Vector Codes
Bipartite Ramanujan graphs (2-lifts MSS'14)
High-dimensional expanders: Random walks (Up and Down walks), Trickle-down, Expansion of bases exchange of Matroids
Phase 3
In this last phase, we will have project presentations. Topics for projects will be selected as we transition from phase 1 to phase 2, with several suggestions available and students encouraged to consult with the instructor.
Topics for Projects
Possible topics include, but are not limited to:
Classical: Agreement Expansion, HDX constructions, Derandomizing Space Bounded Computation, Tree codes, Global Hypercontractivity, Lower bounds on LCCs, Strong bounds for 3-APs, Insertions and Deletions, Reed Muller against BEC and BSC.
Lecture notes will be posted tentatively every week after classes.
Notes here (under construction).
Lecture 1: Overview of the course, some notions of expansion (e.g., edge and vertex expansion), recalling the spectral theorem from linear algebra,
and pseudorandom properties of expanders (e.g., expander mixing lemma).
Lecture 2: We recalled the previous lecture, introduced the random walk operator, proved mixing bounds of random walks,
introduced Cheeger's inequality, and very briefly mentioned the Laplacian matrix.
Lecture 3: Quadratic form and its connection to the spectral decomposition. Optimization/variational characterization of
eigenvalues, including the Courant-Firscher-Weyl min-max theorem. Relating the spectrum of principal submatrices (in particular, induced subgraphs)
via Cauchy interlacing theorem. Recursive definition of the adjacency matrix of the Boolean hypercube. Introduced Boolean functions and two complexity
measures: sensitivity and block sensitivity. Stated the (now resolved) sensitivity conjecture.
Lecture 4: Introduced Fourier analysis of Boolean functions with characters, their orthogonality, and Fourier decomposition. Introduced the complexity
measures of degree and approximate degree. Discussed the classical and quantum query model with the decision trees and quantum oracle model. Introduced
associated complexity measures D(f) and Q(f), and their connection to degree and approximate degree. Polynomial relation among complexity measures. Implications
to Grover's algorithm and quantum speed-up for total functions. Introduced edge signing of graphs. Presented Huang's proof of the sensitivity conjecture using
the spectral graph theory toolkit developed so far.
Lecture 5: Various properties of the Fourier transform (Parseval, variance, etc). Convolution and its Fourier transform. Characters as homomorphisms.
Characters as the eigenfunctions of the Boolean hypercube. Property testing with the case of linearity testing. The BLR linearity test, and its Fourier analytic
proof.
Lecture 6: A case of study of pseudorandomness through the fundamental notion of epsilon-biased distributions and their power in fooling some classes of functions.
Cayley graphs, an important class of graphs defined from a group and a set of generators. A reminder of characters as eigenfunctions of Cayley graphs with the case of Z_2^n.
The equivalence of an epsilon-biased distribution and a two-sided Cayley expander over Z_2^n. Started introducing coding theory with the notions of code, Hamming distance, and rate.
Grading
This is an advanced graduate topics course, so the primary goal is to develop your research maturity and increase your knowledge and skills. Grades will be a secondary concern. We do expect you to seriously attack your chosen research project, but there is no requirement of a tangible outcome.
Policy
Project: 80%
This will consist in selecting a research problem or paper related to the course in consultation with the instructor.
Students can either work in pairs or individually. The outcome should be a short research paper on the chosen topic (this
can range from a survey to an original result ;), and a presentation towards the end of the course.
In summary, a project will consist of the following:
Selection of the research topic: consult the instructor to find a problem or paper aligned with your interests
and the scope of the course. This can occur at any point (ideally, as we transition from phase 1 to 2).
Mid-project feedback: collect the instructor's feedback on the progress of the project at approximately
1 month before the end of the course.
Research paper + presentation towards the end of the course.
Participation: 20%
This includes attendance, curiosity, asking questions during class or office hours, etc.
Additional Material
We will not follow any particular book or resource in this course. However, there are many great additional resources for further study, depending on your interests.
A sample is given below (in no particular order).