Selected Topics in Computational Complexity

General Information

• 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

1. 23-Feb. Lecture 01 – StrongP vs StrongNC.
2. 2-Mar. Parametric Complexity: an approach to proving lower-bounds for the model.
3. 09-Mar.Exponential lower-bound on the parametric complexity of max-flow.
4. 16-Mar. Finishing the proof of the lower-bound for the linear variant. Lecture notes.
5. 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)
6. 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.
7. 27-Apr. Proof of Gordan’s Transposition Theorem and – minus one lemma – Sherstov’s threshold-degree-discrepancy theorem. Lecture Notes.
8. 11-May. An explicit  function with high threshold degree (Minsy & Papert, 1967). Lecture Notes.
9. 18-May. The cell-probe model, and the chronogram method for proving data structure lower bounds in it. Lecture Notes.

Advertisement