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

### Like this:

Like Loading...