Graduate Computational Complexity

Fall 2010

Institute for Theoretical Computer Science, Tsinghua University
Instructor: Periklis A. Papakonstantinou []
Teaching assistant: Youming Qiao
Lectures: Wednesday and Friday 3.20-5pm, FIT 1-222
Office hours: Wednesday 1-3pm (or by appointment)


[Dec 27] Problem-sets #13 and #14 are posted (the 14th is essentially bonus)
[Dec 27] Final exam: Thursday January 13th, from 10am to 6pm (lunch will be provided)

Handouts and problem-sets

Course Blog

Discussion forum


Date Topic
Dec 31 Natural proofs and algebrization: the wild world of barriers in proving lower bounds.
Dec 29 Introduction to two-party Communication Complexity. Applications to streaming lower bounds and time-space tradeoffs.
Dec 24 An introduction to algebraic complexity theory by Youming
Dec 22 The fundamental theorem of private-key crypto: equivalence of PRGs - OWFs - PRFGs. The Goldreich-Levin hardcore bit theorem. Elements of PCPs and holographic proofs.
Dec 17 Introduction to foundations of Cryptography, intractability assumptions, private vs public-key crypto, can we get public-key crypto from OWFs?
Dec 15 Interactive computation, AM=AM[2], is Graph Isomorphism NP-complete? , arithmetization, IP=PSPACE, program checkers
Dec 10 Exponential monotone circuit lower bounds for CLIQUE.
Dec 8 Finish-up the proof of the switching lemma.
Dec 3 Hastad's switching lemma. PARITY not in AC^0.
Dec 1 Back to non-randomized computation: revisiting PH and the Karp-Lipton theorem, Alternating Turing Machines, the nature of PH - relations to circuit families, more results in concrete Circuit Complexity.
Nov 26 From hard functions to pseudorandom generators, the Nisan-Wigderson pseudorandom generator, Kabanets-Impagliazzo (details on KI by Youming in next week's recitation)
Nov 24 Introduction to pseudorandom generators, PRGs in cryptography vs PRGs in complexity theory. Yao's unpredictability implies pseudorandomness.
Nov 21
(4 hrs)
Hardness amplification, Yao's XOR lemma, Impagliazzo's hardcore lemma, applying ECC to obtain average from worst-case hardness.
Nov 19 BPP contained in P/poly and Sigma(2) intersect Pi(2)
Nov 17 Hitting property of expander RWs, introduction to the polynomial hierarchy.
Nov 12 UREACH in LOGSPACE (the details on the zig-zag product in the recitation), reducing randomness in efficient computation through RWs, other applications of expander graphs.
Nov 10 Notions of pseudo-randomness, statements about random objects, sides of error RP, coRP, BPP, main properties and common fallacies.
Nov 5 Random walks on finite graphs and expander graphs, the spectrum of an undirected graph, notions of expansion and their relations
Nov 3 Elements of the probabilistic method, pseudo-random objects, introduction to expander graphs, existence of bipartite expanders, expander mixing lemma, randomness in efficient computation vs randomness in cryptography, distributed computing...
Oct 29 Savitch's theorem, QBF is complete for PSPACE, RL and complete problems
Oct 22 Verifying NP-witnesses with limited resources, one vs two-way non-deterministic tape, inductive counting, NL=coNL
Oct 20 Complete problems for P, space bounded computation, Turing Machine space and circuit depth, NL-completeness
Oct 15
Uniform vs non-uniform circuits, the NC and AC hierarchies, the role of reductions, new types of reductions, more relations and more conjectures
Oct 13
Proof of Cook-Levin, NP-completeness and self-reducibility, formulas vs circuits, introduction to space-bounded computation
Oct 9 Ladner's theorem, candidates between P and NP-complete, more on non-determinism, proofs and certificates, computation is local, Cook-Levin (proof sketch)
Oct 8 Baker/Gill/Solovay theorem, Ladner's theorem (proof sketch)
Sept. 29 Oracle Turing machines, relativization, Baker/Gill/Solovay theorem (begin), non-determinism
Sept. 26
(4 hrs)
Constructibility, padding, space/time hierarchy and consequences. Oracles and relativization
Sept. 17 Introduction: models of computation, resources, Turing Machines, speedup/tape compression