Expanders and Pseudorandom Graphs

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Mondays 10am-12noon, EM 119 (Note the nonstandard location: Emmanuel College near the ROM)
TA: Devansh Shringi (devansh.shringi@mail.utoronto.ca)

Please email me if you are not registered and want to be added to the mailing list.
Please use the course piazza site for questions and discussions.

This course is about various kinds of pseudorandom graphs such as expander graphs. These are graphs that appear to be random - a single graph that shares properties with most graphs. There is a rich and interesting theory with applications to many topics in theoretical computer science and discrete math. It will also be an opportunity to see many interesting and general-purpose probabilistic, algebraic and analytic tools. Some possible topics:

• Graph eigenvalues and combinatorial aspects
• Expander graphs: constructions, theory, applications to derandomization of algorithms
• Pseudorandomness of dense graphs, the Szemeredi regularity lemma.
• High dimensional expanders
• Applications to extremal combinatorics

Homework

Scribing

Papers for projects

List of Papers for Projects,

Lectures

• September 9: probability warmup, triangles in G(n,p), the zero-one law for G(n,p) (notes)
• September 16: the zero-one law for G(n,p) continued, the number of C_4 in a graph with given edge density
• September 23: linear algebra warmup, graph eigenvalues, quasirandomness for dense graphs
• September 30: quasirandomness - discrepancy, eigenvalues, subgraph counts. Szemeredi regularity lemma (the statement), triangle removal lemma.
• October 7: Random walks on graphs, (absolute eigenvalue) expanders, expander mixing lemma, edge expansion.
• October 14: NO CLASS - Thanksgiving
• October 21: error reduction via (1) expander neighborhoods, (2) expander walks
• October 28: NO CLASS - Reading Week
• November 4: undirected connectivity, Savitch's theorem, definition of the Replacement product + Zig-Zag product, explicit expanders
• November 11: Analysis of the Zig-Zag product. Undirected connectivity in log space. superconcentrators and circuit lower bounds.
• November 18: Cayley Graphs, Fourier analysis on abelian groups, expansion of Cayley graphs
• November 25: Bipartite vertex expansion, connection to eigenvalue expansion, probabilistic construction, epsilon biased sets, basic expander codes + decoding
• December 2: Miscellaneous advanced topics
• December 3 (Tuesday): Bonus class - Project presentations