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 A \in \mathcal A can solve problem X, where \mathcal A 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 \mathrm{AC}_0 (depth-3 majority circuits can).
  • The Chronogram Method of Fredman & Saks. The dynamic range problem requires \log n / \log \log n 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 \mathrm{AC}^0 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 \mathrm{AC}^0 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s