This course investigates problems in computational complexity that can be solved using ideas and techniques from combinatorial analysis.
The topic varies considerably between offerings. In some years, the course has
focused almost entirely on the theory of probabilistically checkable proofs.
The topics below have also been covered in some recent years.
Circuit Complexity: Monotone Circuits, Bounded Depth Circuits, Threshold Formulas.
Explicit Constructions: Expander Graphs, Threshold Formulas, Traversal Sequences.
Communication Complexity: Deterministic and Randomized Protocols
Interactive Proof Systems: Aproximation and Consequences.
Biweekly homework assignments.