- Reading material: Various sources. See below for some links.
- Some familiarity with computational complexity is required. Computation, circuits, etc.
Course Description & Syllabus
Computational Complexity tries to understand how many resources a computer needs in order to solve a given problem. In this course we will be interested in proving things like no algorithm can solve problem , where is a relevant class of algorithms.
In the course we have shown:
- Ketan Mulmuley’s Lower Bound. You cannot solve the weighted maximum-flow problem in parallel – unless you do weird bit-operations on the edge-weights, which no known graph algorithm actually does.
- Sherstov’s Degree-discrepancy Theorem. And its corollary that depth-2 majority-of-threshold circuits cannot decide all of (depth-3 majority circuits can).
- The Chronogram Method of Fredman & Saks. The dynamic range problem requires query or update time (in the cell-probe model).
Summaries and Lecture Notes
- 23-Feb. Lecture 01 – StrongP vs StrongNC.
- 2-Mar. Parametric Complexity: an approach to proving lower-bounds for the model.
- 09-Mar.Exponential lower-bound on the parametric complexity of max-flow.
- 16-Mar. Finishing the proof of the lower-bound for the linear variant. Lecture notes.
- 23-Mar. (a) Careful analysis of the complexity-4 construction of the max-flow parametrization. (b) Proof that circuits can be simulated by quasi-polynomial-size depth-3 majority circuits. We will be proving that depth-2 majority circuits require exponential size. (paper with proof)
- 30-Mar. Communication complexity, discrepancy, threshold degree. Relating discrepancy and computability by MAJ of THR circuits. A nice corollary of Gordan’s Transposition Theorem. Lecture Notes.
- 27-Apr. Proof of Gordan’s Transposition Theorem and – minus one lemma – Sherstov’s threshold-degree-discrepancy theorem. Lecture Notes.
- 11-May. An explicit function with high threshold degree (Minsy & Papert, 1967). Lecture Notes.
- 18-May. The cell-probe model, and the chronogram method for proving data structure lower bounds in it. Lecture Notes.