CS359A: Research seminar on complexity theory

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

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.

• 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
  Mossel-O'Donnell-Servedio
  Valiant's light bulb problem

References will be provided. For now, see this link.