**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**

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

Advertisements