Computational Complexity 2021

Lectures

Videos of lectures 1—6 on Yandex Disk.

1. 2021-09-02: recap of basic definitions, decision vs search, padding (EXP ≠ NEXP implies P ≠ NP), existence of NP-intermediate problems (Ladner’s theorem). Notes. See also [AB09] Sections 2.6, 3.3.

2. 2021-09-09: oracles, existence of oracles such that P^A = NP^A and P^B ≠ NP^B, polynomial hierarchy. Notes. See also AB09 Sections 3.4, 5.1, 5.2.

3. 2021-09-16: equivalence of PH definitions, circuits, equivalence of circuits and TMs with advice, Karp-Lipton theorem (NP ⊆ P/poly ⇒ PH = Σ_2 P). Notes. See also AB09 Sections 5.5, 6.1—6.4.

4. 2021-09-23: AC and NC hierarchies, switching lemma. Notes. See also Juk12 Section 12.2.

5. 2021-09-30: Parity not in AC0. Randomized computation. Notes. See also Juk12 Section 12.2, AB09 Sections 7.1—7.4.

6. 2021-10-07: BPP in P/poly and PH (Gács-Lautemann-Sipser). Interactive Proofs. Graph non-isomorphism in IP. Notes. See also AB09 Sections 7.5, 8.1.

7. 2021-10-14: Zero-knowledge proofs. ZK proof for graph isomorphism. Public coin interactive proofs (AM). Intuition for Goldwasser-Sipser set lower bound protocol. Notes. See also Gol08 Section 9.2, AB09 Section 8.2.

8. 2021-10-21: Goldwasser-Sipser set lower bound protocol. AM proof for graph non-isomorphism. Simple cases of IP[k] ⊆ AM[k+2]. Notes. See also Gol08 Sections 9.2, F.2.1.

9. 2021-10-28: IP = PSPACE. Notes. See also Gol08 Section 9.1.3, AB09 Section 8.3.

10. 2021-11-11: #P, Valiant-Vazirani theorem (USAT ∈ RP ⇒ RP = NP), base case of Toda’s theorem. Notes. See also AB09 Chapter 17.

11. 2021-11-18: Toda’s Theorem. Pseudo-Random Generators. Notes. See also AB09 Sections 17.4, 20.1.

12. 2021-11-25: Pseudo-Random Generators from average-hard functions (Nisan-Wigderson PRG). Notes See also AB09 Section 20.2.

13. 2021-12-02: Expander graphs. Error reduction using few random bits. Notes See also AB09 Sections 21.1, 21.2.

14. 2021-12-09: s-t Connectivity in L. Replacement Product. Notes See also AB09 Sections 21.3, 21.4.

15. 2021-12-16: Probabilistically Checkable Proofs and hardness of approximation. Notes See also AB09 Sections 11.2, 11.3, 11.5.

16. 2021-12-17: NP ⊆ PCP(poly(n),O(1)). Linearity testing. Notes See also AB09 Sections 11.5, 22.5.

Practice

1. 2021-09-06: Ladner’s theorem, unary languages. Notes.

2. 2021-09-13: oracles, class DP. Notes.

3. 2021-09-20: oracles where P ≠ NP with high probability, upper bounds on circuit size, basic bound on circuits for parity. Notes.

4. 2021-09-27: languages in PH/EXP that require large circuits, majority not in AC0, optimal AC0 circuit for parity. Notes.

5. 2021-10-04: weak switching lemma, corner cases of randomized computation, random walk algorithm for 2SAT. Notes.

6. 2021-10-11: biased coins, variations on the definition of IP.

7. 2021-10-18: BPP ⊆ S_2 P, BPP ⊆ ZPP^NP, PH collapses if coNP ⊆ AM[2].

8. 2021-10-25: hash functions, ZK requires interaction, IP[2] ⊆ AM.

9. 2021-11-01: IP and AM with RP and coRP verifiers. Notes

10. 2021-11-08: #3SAT in IP, IP=PSPACE without linearization, MA ⊆ AM.

11. 2021-11-15: counting problems.

12. 2021-11-22: counting problems.

13. 2021-11-29: pseudorandomness.

14. 2021-12-06: pseudorandomness.

15. 2021-12-13: expander graphs.

16. 2021-12-20: expander mixing lemma, inapproximability of independent set, optimality of the PCP theorem.

Course Plan

Topics

Nondeterministic and randomized computation

• Search and decision problems; Levin’s search algorithm
• NP-intermediate problems: graph isomorphism, factoring, existence (Ladner’s theorem).
• Polynomial hierarchy, conditions for collapse
• Schwartz-Zippel lemma, polynomial identity testing
• Relation between BPP and polynomial hierarchy (Sigma_2, S_2, ZPP^NP)
• Valiant-Vazirani lemma (USAT ∈ P implies NP = RP)
• Toda’s theorem (PH ⊆ P^#SAT)
• Average-case complexity

Interactive protocols

• Interactive protocols, graph isomorphism, permanent
• Private vs public coin protocols (Goldwasser-Sipser, IP[k] ⊆ AM[k+2])
• One-sided vs two-sided error
• Relation between IP and polynomial hierarchy
• Round reduction (AM[k] ⊆ AM[2])

Low-complexity classes, pseudorandomness

• Parallel algorithms
• Relation between low-space machines and low-depth circuits (L, NL, NC)
• Randomness amplification using expander graphs
• Nisan’s pseudorandom generator
• PCP theorem, hardness of approximation
• MIP = NEXP

References:

The main reference is the book:

• Computational Complexity: A Modern Approach. Arora, Barak.

Complementary books include:

• Computational Complexity. Papadimitriou.
• Introduction to the Theory of Computation. Sipser.
• Классические и квантовые вычисления. Китаев, Шень, Вялый.
• Boolean Function Complexity. Jukna.
• Computational Complexity: A conceptual perspective. Goldreich.

Many similar courses have useful lecture notes publicly available on the web.