CS 598: Expansion, Codes, and Optimization both Classical and Quantum

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
• Fourier Analysis: Basics (Fourier decomposition, Parseval, etc), BLR, biased distributions and codes, Hypercontractivity
• 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.
• Quantum: Quantum PCP, Locally Testable Quantum Codes, SYK and Sum-of-Squares, Pseudorandom Unitaries, Quantum Expanders.