CS359A: Research seminar on complexity theory

General Information

Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
Time: Tuesdays and Thursdays 4:30-5:50pm

Seminar description

A research seminar on concrete complexity theory.

We will study powerful and versatile techniques for analyzing basic models of computation — decision trees, DNF formulas, halfspaces, and juntas — and see applications of these techniques to a variety of areas including circuit lower bounds, derandomization, quantum complexity, learning theory, and applied probability.

A major focus of the seminar will be on mapping out the research frontier and developing fruitful research directions. In the final few meetings of the quarter we will tackle research problems together.

Topics covered

  • Decision trees
    Query complexity and relationships among complexity measures
    Every decision tree has an influential variable
    The Aaronson-Ambainis conjecture and the power of quantum computation
    P = NP ∩ coNP for decision trees
    The sensitivity theorem
  • DNF formulas
    Random restrictions and switching lemmas
    Linial-Mansour-Nisan: Fourier spectrum of DNF formulas
    Mansour's conjecture and its implications
    Razborov-Smolensky polynomial approximators
    Bazzi's theorem: Bounded independence fools DNFs
    Fredman-Khachiyan and the monotone dualization problem
  • Halfspaces
    Noise sensitivity of halfspaces
    Halfspaces and the Central Limit Theorem
    Mossel-O'Donnell-Oleszkiewicz Invariance Principle
    The Gotsman-Linial conjecture
    Bounded independence fools halfspaces
  • Juntas
    Learning in the presence of irrelevant information
    Valiant's light bulb problem
References will be provided. For now, see this link.

Seminar format

•  First few meetings: Li-Yang will give an overview of the topics listed above
•  Bulk of the quarter: Student-led deep dives into specific topics and results
•  Final few meetings: Research discussions


(Tentative; more details to follow.)
•  Discussion lead for 1-2 meetings
•  Short summaries of meetings
•  Class participation
Since in-class discussions are a crucial component of this seminar, attendance will be expected.
(Seminar meetings will not be recorded.)