Skip to content Skip to navigation

Combinatorial Methods In Complexity Theory

16:198:540

This course investigates problems in computational complexity that can be solved using ideas and techniques from combinatorial analysis.

Credits: 
3
Category: 
A
Prerequisite: 

16:198:50916:198:513, or permission of instructor.

Topics: 

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.

Current Literature.

Expected Work: 

Biweekly homework assignments.

Semester: 
Spring
Course Type: 
Graduate

Check the University Schedule of Classes to see if this course is open.

Request a Special Permission Number here if the class is full.