Course Details

  • Course Number: 16:198:540
  • Course Type: Graduate
  • Semester 1: Spring
  • Credits: 3
  • Description:

    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
  • 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.