16:198:540 - Combinatorial Methods In Complexity Theory
- Course Number: 16:198:540
- Course Type: Graduate
- Semester 1: Spring
- Credits: 3
This course investigates problems in computational complexity that can be solved using ideas and techniques from combinatorial analysis.
- M.S. Course Category: Algorithms & Complexity
- Category: A (M.S.), A (Ph.D.)
- Prerequisite Information:
16:198:509, 16:198:513, or permission of instructor.
- Course Links: 16:198:509 - Foundations of Computer Science, 16:198:513 - Design and Analysis of Data Structures and Algorithms
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.
- Expected Work: Biweekly homework assignments.