Topics in Complexity Theory

• Instructors : Arnab Bhattacharyya, Chandan Saha   Course number and Credits : E0 309 and 3:1   Lecture time : M,W 3:30-5 pm   Venue : CSA 252


• Motivation & objective : The theme of this course (in the Jan-April semester of 2014) is ``Expander graphs and their applications". Expander graphs are highly interesting combinatorial objects with some striking applications in computer science (particularly in complexity theory and network designs). Loosely speaking, expanders are ``sparse graphs" (i.e. with not too many edges) that are ``highly connected". What makes the concept of graph expansion so versatile is that it can be equivalently defined using the languages of combinatorics, algebra, geometry and probability. The aim of this course is to give a mathematical introduction to the property of graph expansion along with an exposition of some of the applications of expander graphs in computer science - for example, in derandomization, construction of error correcting codes, algorithmic results in compressed sensing, proof of the PCP theorem and so on.


• Syllabus :
  • Introduction to expander graphs
    • Graph expansion & eigenvalues (combinatorial and spectral definitions)
    • Random walks on expanders
    • Rayleigh quotient, Cheeger's inequality
    • Examples of explicit constructions
  • Applications
    • Expander-based error-correcting codes
    • Sparse signal recovery from expanders
    • Higher-order Cheeger's inequalities & spectral partitioning
    • Zig-zag product and undirected connectivity in logspace
    • Dinur's proof of the PCP theorem
    • (if time permits) Randomness extractors


• References :
  1. A survey on expanders by Shlomo Hoory, Nathan Linial and Avi Wigderson
  2. A survey on Pseudorandomness by Salil P. Vadhan
  3. A course on expanders offered by Cynthia Dwork and Prahladh Harsha
  
  
• Prerequisites : Familiarity with basic linear algebra, probability theory and algorithms will be helpful. More importantly, we expect some mathematical maturity with an inclination towards theoretical computer science.


• Assignments :
  • Assignment 1 (due date: Feb 12, 2014)


• Lectures :
  • Lecture 1: Introduction to graph expansion; Combinatorial definition of expansion; Existence of expanders using probabilistic methods (magical graphs); Construction of superconcentrators with O(n) edges.
  • Lecture 2: Applications of expanders - contruction of error correcting codes; Error probability reduction for class RP; Examples of explicit constructions of expander families.
  • Lecture 3: Graph spectrum and algebraic definition of expansion; Statement of Cheeger's inequality; Expander mixing lemma; Some applications of the expander mixing lemma
  • Lecture 4: Alon-Boppana bound on spectral gap - proof of a weaker version; Comparison between the combinatorial and algebraic definiton of expansion; Random walks on expanders - rapid mixing of walks
  • Lecture 5: Random walks resemble independent sampling; Application (1a) - Amplifying the success probability of one-sided error probabilistic algorithms
  • Lecture 6: Application (1b) - Amplifying the success probability of two-sided error probabilistic algorithms; Application (2) - Hardness of approximating max clique
  • Lecture 7: Rayleigh quotient; The Discrete Laplacian; Proof of Cheeger's inequality - large spectral gap => high expansion
  • Lecture 8: Cheeger's inequality (contd.) - high expansion => large spectral gap; Alon's upper bound on expansion; Discussion on small set expansion