Graduate Computational Complexity Theory
Course documents
Lectures
Lecture 1: Overview
Lecture 2: Hierarchy Theorems
Lecture 3: Circuits
Lecture 4: Probabilistic Complexity Classes
Lecture 5: Polynomials in Complexity Theory
Lecture 6: Time in Square-Root Space
Lecture 7: Constant-Depth Circuit Lower Bounds (Even with MOD Gates)
Lecture 8: Hardness vs. Randomness I
Lecture 9: Hardness vs. Randomness II
Lecture 10: Hardness Amplification
Lecture 11: The Polynomial Hierarchy
Lecture 12: The Hierarchy, Oracles, and Circuits
Video 1's
Switching Lemma via Downward-Closed Conditioning (Liam)
$\mathrm{OR}_n$ is computable by a depth 3, $\mathrm{MOD}_6$ circuit of size $2^{O(\sqrt{n})}$ (Zachary)
Barrington's Theorem: Width 5 Branching Problems = $\mathsf{NC}^1$ (Spencer)
Deciding Palindromes on a 1-Tape TM in $O(n \log n)$ Time with a Randomized Algorithm (Kailey)
Palindromes on a two-dimensional tape require $\Theta(n^2/\log n)$ time (Daniel Q)
Determinant and Matrix Inversion are in $\mathsf{NC}^2$ (Trevor)
Parity Requires Formulas of Size $\Omega(n^{3/2})$ (Kelsey)
$O(n)$-size, $O(\log n)$-depth circuits are computable by depth-3 circuits of size $2^{O(n / \log \log n)}$ (Juho)
Sorting Networks of Polylogarithmic Depth (Yusuf)
Sorting Networks in Logarithmic Depth (Junkai)
Undirected Connectivity in Deterministic Logspace (Junzhao)
$\mathsf{BPL}$ is a subset of $\mathsf{SPACE}(\log^{3/2} n)$ (Yang)
An explicit function requires formulas of size $\Omega(n^{5/2})$ (Liran)
SAT is Complete for Nondeterministic Quasilinear Time, even for RAMs (Zelong)
Nisan's Pseudorandom Generator (Shenghao)
Time Travel Classes and $\mathsf{BPP}_{\mathrm{path}}$ (Sriram)
If $\mathsf{EXP} \not\subseteq \mathsf{P}/\mathsf{poly}$, then some $L \in E$ has average-case circuit hardness $1/\mathrm{poly}(n)$ (Nuozhou)
Circuit Lower Bound from Learning (Devangi)
Probabilistic Savitch's Theorem: $\mathsf{PrSPACE}(S) \subseteq \mathsf{SPACE}(S^2)$ (Chris)
Polynomial-size Circuits are Learnable in ${\mathsf{ZPP}}^{\mathsf{NP}}$ (Anurag)
$\mathsf{P}^{\mathsf{NP}[\log]} = {\mathsf{P}}_{\|}^{{\mathsf{NP}}}$ (Anthony)