MATH/CMSC 38800: Complexity Theory

Spring 2025: Tuesday, Thursday 2pm-3:20pm Eckhart 202

Office hours: by appointment (this is an advanced graduate course...). Preferred ways:
- If your question(s) can be asked in a concise form, ask them on Ed Discussion. This way, they will be answered promptly and an interesting discussion may ensue from which everyone will benefit.
- On most days, I am free after the lecture, usually this results in a meaningful Q/A session.

Courtesy of Yakov Shalunov, lecture notes are available here. So far the first two weeks have been verified, more are (eventually) coming.

Homeworks. There will be three homework assignments. No quizzes/exams.

Literature. Our main reference is [1] (referred to as [AroraBarak] hereafter).
1. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
2. A. Razborov, Foundations of computational complexity theory, Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, No. 321, 2005, pages 186-202.
3. M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, Third Edition, 2008.
4. N. J. Cutland, Computability, Cambridge University Press, 1980.
5. G. Ausiello, Difficult logical theories and their computer approximations, Asterisque, 38-39: 3-21. 1976.
6. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
7. K. L. Manders, L. Adleman, NP-Complete decision problems for binary quadratics, Journal of Computer and System Sciences, 16(2), 168-184, 1978.
8. A. Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution, Annals of Mathematics, 181(2), 415-472, 2015.
9. I. Oliveira, Meta-Mathematics of Computational Complexity Theory, 2025.
10. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2010.
11. C. H. Bennetts, J. Gill, Relative to a Random Oracle A, P^A \neq Np^A \neq co-Np^A with Probability 1, SIAM Journal on Computing, 10(1): 96-113 ,1981.
12. L. Babai, S. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, J. Comput. Syst. Sci., 36(2): 254-276, 1988.
13. S, Jukna, Boolean functions complexity, Springer-Verlag, 2012.
14. A. Razborov, Lower Bounds for Deterministic and Nondeterministic Branching Programs, in Proceedings of the 8th FCT, Lecture Notes in Computer Science, vol. 529, 1991, 47--60.
15. S. Cook, A Taxonomy of Problems with Fast Parallel Algorithms, in Information and Control, 64: 2-22, 1985.
16. K. Iwama, H. Morizumi An explicit lower bound of 5n-o(n) for boolean circuits, in Proceedings of the MFCS 2022, Springer LNCS, vol. 2420, 353-364.
17. M. Find, A. Golovnev, E. Hirsch, A. Kulikov, Improving Circuit Complexity Lower Bounds, in Computational Complexity, vol. 32, no 13, 2023.
18. A. Razborov, On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52.
19. M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 2009.
20. A. Razborov, S. Rudich, Natural Proofs, in Journal of Computer and System Sciences, 55(1):24-35, 1997.
21. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
22. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
23. M. Goos, T. Pitassi, T. Watson, Deterministic Communication vs. Partition Number, in SIAM Journal on Computing, 47(6), 2435-2350, 2018.
24. I. Newman, Private vs. common random bits in communication complexity, in Information Processing Letters, 39(2), 67-71, 1991.
25. R. Paturi, J. Simon, Probabilistic Communication Complexity, in Journal Of Computer And System Sciences, 33, 106-123, 1986.
26. V. Strassen, Algebraic Complexity Theory, Chapter 11 of Handbooks of Theoretical Computer Science, Volume A (Algorithms and Complexity), 1990.
27. A. Shpilka, A. Yehudayoff, Arithmetic Circuits: A Survey of Recent Results and Open Questions, in Foundations and Trends in Theoretical Computer Science, Vol. 5, No. 3-4, pp 207-388, 2010.
28. A. Razborov, Propositional Proof Complexity, in Proceedings of the 8th European Congress of Mathematics, pp. 439-464, 2023.
29. S. Buss and J. Nordstrom, Proof Complexity and SAT Solving, in Handbook of Satisfiability, 2nd edition, IOS Press, Chapter 7, 2021.
30. D. Grigoriev, E. Hirsch, D.Pasechnik, Complexity of semi-algebraic proofs, Moscow Mathematical Journal, 2(4): 647-679, 2002.

Progress and references.

First week: For a highly informal introduction into classical Turing complexity along the lines we did in class, see [2]. The standard source on Kolmogorov complexity is [3]. Machine-independent complexity, Blum's axioms [4, Ch. 12.1]. Speed-up Theorem (without proof) [4, Thm. 12.2.1]. Complexity classes, DTIME [AroraBarak, Ch. 1.6] or [5, Ch. 7.1]. Gap Theorem (without proof) [4, Thm. 12.3.1]. Time Hierarchy Theorem [AroraBarak, Thm. 3.1]. The "sophisticated" upper bound on the running time of the universal machine [AroraBarak, Thm. 1.9]. Space Hierarchy Theorem (without proof) [AroraBarak, Thm. 4.8]. Relations between time and space [AroraBarak, Thm. 4.2]. Complexity of decidable logical theories: [5] and the references therein. Oracle Turing machines [AroraBarak, Sct. 3.4] and Cook-Turing reductions [AroraBarak, Exerc. 2.14].

Second week: Karp (many-one) reductions [AroraBarak, Ch. 2.2]. Non-deterministic time [AroraBarak, Ch. 2.1.2]. Non-deterministic time hierarchy theorem (without proof) [AroraBarak, Thm. 3.2]. NP [AroraBarak, Ch. 2.1] and the equivalence of two definitions [AroraBarak, Thm. 2.6]. NP-complete problems [AroraBarak, Ch. 2.2]. Universal NP-complete problem [AroraBarak, Thm. 2.9]. Cook-Levin Theorem [AroraBarak, Thm. 2.10]. Web of reductions and examples of NP-complete problems [6, Ch. 7.5] or [AroraBarak, Ch. 2.4], see also Wikipedia article.. Examples of NP-complete problems. 3SAT [AroraBarak, Lemma 2.14]. The problem THEOREMS, along with its philosophical significance, is extensively discussed in [AroraBarak, Sct. 2.7.2]. Bounded version of Hilbert's 10th problem [7]. INDEPENDENT SET [AroraBarak, Thm. 2.15]. Pseudo-polynomial algorithms: [6, Sct. 4.2] or Wikipedia article. For one approach to show independence of P vs. NP from weak logical theories see [8, Sct. 1] and the references therein. Brand new: [9] is way more systematic (and updated) treatment of this subject. The Web of solutions to the P vs. NP problem until 2016 (unfortunately the page does not seem to be being updated any more but the effort strives!): P versus NP page.

Third week: Web of reductions cntd. Vertex Cover and approximation algorithms (very briefly, for an in-depth treatment see [10]). TQBF and its PSPACE-completeness [AroraBarak, Thm. 4.13]. Savitch's theorem [AroraBarak, Ch. 4.2.1]. Ladner's theorem (without proof) [AroraBarak, Ch. 3.3]. Complete problems for EXPTIME: see the Wikipedia article and the references therein. Limits of diagonalization: Baker-Gill-Solovay theorem [AroraBarak, Thm. 3.7]. Polynomial-time hierarchy [AroraBarak, Ch. 5]. Randomized computations [AroraBarak, Ch. 7.1 and 7.3].

Fourth week: Randomized computations cntd. BPP is strange [AroraBarak, Ch. 7.5.3]. Sipser-Gacs theorem [AroraBarak, Thm. 7.15]. Toda's theorem (without proof) [AroraBarak, Thm. 17.14]. Oracle characterization of BPP (and many other things for a random oracle): [11]. Deterministic interactive proofs [AroraBarak, Ch. 8.1.1]. Interactive proofs [AroraBarak, Ch. 8.1]. Quantifier representation of AM [AroraBarak, Figure 8.2]. AM collapses for finitely many rounds [12]. Public coin model is essentially equivalent to the private coin model (without proof) [AroraBarak, Thm 8.12]. Protocol for graph non-isomorphism [AroraBarak, Ch. 8.1.3]. IP=PSPACE (statement) [AroraBarak, Ch. 8.3] (see also "Chapter Notes and History" on page 169).

Fifth week: IP=PSPACE (sketch of the proof). MIP=NEXP (without proof) [AroraBarak, Ch. 8.5]. Probabilistically Checkable Proofs (PCP) [AroraBarak, Ch. 11.2]. Max-3-SAT [AroraBarak, Ch. 11.1]. Two disguises of the PCP theorem [AroraBarak, Ch. 11.2]. Classes L and NL [AroraBarak, Ch. 4.1]. Immerman-Szelepcsenyi theorem (without proof) [AroraBarak, Thm. 4.20]. Log-space reductions, st-connectivity (called PATH in the book) is NL-complete [AroraBarak, Ch. 4.3]. Examples of P-complete problems, including Horn satisfiability. The monograph [13] is highly recommended source on circuit complexity. Boolean circuits [AroraBarak, Ch. 6.1] or [13, Ch. 1.2]. Shannon counting argument [AroraBarak, Thm. 6.21] or [13, Ch. 1.4]. "Fancier" upper bounds on the Shannon function: [13, Theorem 1.15].

Sixth week: Non-uniform hierarchy theorem (in slightly more precise form) [AroraBarak, Thm. 6.22] or [13, Thm. 1.19]. Advice Turing machines and an alternate description of P/poly [AroraBarak, Ch. 6.3]. BPP is in P/poly [AroraBarak, Thm. 7.14]. Karp-Lipton theorem (without proof) [AroraBarak, Thm. 6.19]. Kannan's theorem [AroraBarak, Exc. 6.5 and 6.6]. Circuit depth, relations between size and depth, Spira's theorem [13, Ch. 6.1]. Branching programs and similar models [AroraBarak, Ch. 14.4.4], [13, Part V] or [14]. NC^k and AC^k [AroraBarak, Ch. 6.7.1]; for more interesting classes between NC^1 and NC^2 see [15]. Mini-survey of some lower bounds. General circuits (without proofs) [16] (deMorgan basis), [17] (full binary basis), see also [13, Theorem 1.29] for an earlier result. De Morgan formulas (without proof) [13, Ch. 6.3, 6.4]. Rectangular approach to Khrapchenko's bound [13, Ch. 6.7, 6.8].

Seventh week: Khrapchenko's bound cntd. Nechiporuk's bound [13, Ch. 6.5 and 15.1]. Lower bounds against AC^0 circuits, random restrictions (high-level idea) [AroraBarak, Ch. 14.1] or [13, Ch. 12.1-12.4]. Lower bounds for $AC^0[p]$ circuits, the method of approximations [AroraBarak, Ch. 14.2] or [13, Ch. 12.5-12.6]. Lower bounds for monotone circuits (high-level idea) [AroraBarak, Ch. 14.3] or [13, Ch. 9.10-9.11]. Bounded-depth threshold circuits: [13, Ch. 11.10] or [18]; for connections to the theoretical machine learning see e.g. [19]. Lower bound for the majority of thresholds (without proof) [13, Theorem 11.37]. Threshold of majorities, reduction to sign-rank [13, Claim 11.40]. Forster's bound on sign-rank (without proof) [13, Theorem 4.42]. Natural Proofs (high-level overview) [20] or [AroraBarak, Ch. 23].

Eighth week: Communication complexity is covered in a great deal of sources: [13, Part 2], [21], [22] or [AroraBarak, Ch. 13]. Combinatorial rectangles and tiling complexity [AroraBarak, Ch. 13.2.2] or [13, Ch. 3.1-3.2]. A separation between tiling complexity and communication complexity, lifting techniques (without proof) [23]. Rank lower bound [AroraBarak, Ch. 13.2.3] or [13, Ch. 4.5]. Log-rank conjecture [AroraBarak, Ch. 13.2.6] or [13, Ch. 4.6]. Non-deterministic communication complexity [13, Ch. 4.2]. Relations between deterministic and non-deterministic complexities [13, Theorems 4.9, 4.10]. Karchmer-Wigderson games [13, Ch. 3.3]. Relation between them and formula depth [13, Theorems 3.13, 3.17]. Lower bounds for monitone formulas: top-down approach [13, Ch. 7.4-7.6] and bottom-up approach [13, Ch. 7.1-7.3]. Private vs. public coins in communication complexity [21], [24]. Rabin-Yao protocol for the equality function [21] or [22, Theorem 5]. Unbounded error probabilistic communication complexity vs. sign-rank [25]. Algebraic complexity [AroraBarak, Ch.16], [26] or [27]. The degree bound (without proof) [26, Sct. 6].

Ninth week: Baur-Strassen Lemma [26, Sct. 7]. Valiant's complexity classes [AroraBarak, Ch. 16.1.4]. Propositional proof complexity [AroraBarak, Ch. 15] or [13, Part VI]. Our high-level introduction was primarily based on [28]. For more information about connections with practical SAT solving see [29], and for the menagerie of algebraic and semi-algebraic proof systems see [30]. Size-width tradeoff for resolution [13, Ch. 18]. A few other sources:
- A (highly subjective) list of open problems that I find important. Significantly updated on 5/23/25.
- The Web page of my topic course that also includes some lecture notes.