• If your question(s) can be asked in a concise form, ask them on Ed Discussion. This way, they will be answered promptly and everybody will benefit ftom this.
• On most weeks, I am free after the class until 11:30am. Stay on to talk.

• Assignment #1, due April 21
• Assignment #2, due May 7
• Assignment #3, due May 19

Our main reference is [1] (referred to as [AroraBarak] hereafter); others will be added here as we are making progress.

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. M. Sipser, Introduction to the Theory of Computation, Cengage Learning, Third Edition, 2012.
6. G. Ausiello, Difficult logical theories and their computer approximations, Asterisque, 38-39: 3-21. 1976.
7. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
8. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2013.
9. 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.
10. 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.
11. S, Jukna, Complexity of Boolean functions, Springer-Verlag, 2012.
12. 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.
13. S. Cook, A Taxonomy of Problems with Fast Parallel Algorithms, in Information and Control, 64: 2-22, 1985.
14. E. Viola, Correlation bounds for polynomials over {0,1}, in ACM SIGACT News, 40(1), 2009.
15. A. Razborov, On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52.
16. M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 2009.
17. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4): 612-625, 2002.
18. A. Razborov, S. Rudich, Natural Proofs, in Journal of Computer and System Sciences, 55(1):24-35, 1997.
19. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
20. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
21. M. Goos, T. Pitassi, T. Watson, Deterministic Communication vs. Partition Number, in SIAM Journal on Computing, 47(6), 2435-2350, 2018.
22. I. Newman, Private vs. common random bits in communication complexity, in Information Processing Letters, 39(2), 67-71, 1991.
23. R. Paturi, J. Simon, Probabilistic Communication Complexity, in Journal Of Computer And System Sciences, 33, 106-123, 1986.
24. V. Strassen, Algebraic Complexity Theory, Chapter 11 of Handbooks of Theoretical Computer Science, Volume A (Algorithms and Complexity), 1990.
25. 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.
26. J. Alman, V. Vassilevska-Williams, A Refined Laser Method and Faster Matrix Multiplication, in Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 522-539, 2021.
27. A. Razborov, Proof Complexity and Beyond, SIGACT News, 47(2):66-86, 2016.
28. A. Razborov, Propositional Proof Complexity, to appear in Proceedings of the 8th European Congress of Mathematics, 2021.
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.

• First week: For a highly informal introduction into classical Turing complexity 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]. Gap Theorem (without proof) [4, Thm. 12.3.1]. Complexity classes, DTIME [AroraBarak, Ch. 1.6] or [5, Ch. 7.1]. Time Hierarchy Theorem [AroraBarak, Thm. 3.1] or [5, Thm. 9.10]. Complexity of decidable logical theories [6].
• Second week: Oracle Turing machines [AroraBarak, Sct. 3.4] and Cook reductions [AroraBarak, Exerc. 2.14]. Karp (many-one) reductions [AroraBarak, Ch. 2.2]. Strong Church-Turing thesis, surrounding controversy, discussions etc. [AroraBarak, Ch. 1.6], [5, Ch. 7.2] or [2]. Space-bounded computations, classes L and PSPACE [AroraBarak, Ch. 4.1]. Space Hierarchy Theorem (without proof) [5, Thm. 9.3]. Relations between time and space [AroraBarak, Thm. 4.2]. Non-deterministic time [AroraBarak, Ch. 2.1.2]. NP [AroraBarak, Ch. 2.1] and the equivalence of two definitions [AroraBarak, Thm. 2.6]. NP-complete problems [AroraBarak, Ch. 2.2]. Ladner's theorem (without proof) [AroraBarak, Ch. 3.3]. Universal NP-complete problem [AroraBarak, Thm. 2.9]. Cook-Levin Theorem [AroraBarak, Thm. 2.10].
• Third week: Web of reductions and examples of NP-complete problems [7], [5, Ch. 7.5] or [AroraBarak, Ch. 2.4], see also Wikipedia article. Levin reductions [AroraBarak, Sct. 2.3.6]. Examples of NP-complete problems. Vertex Cover and approximation algorithms [8]. Pseudo-polynomial algorithms: [7, Sct. 4.2] or Wikipedia article (let me know if you are aware of a good recent monograph). TQBF and its PSPACE-completeness [AroraBarak, Thm. 4.13]. Savitch's theorem [AroraBarak, Ch. 4.2.1].
• Fourth week: 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]. 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]. Horn satisfiability is P-complete. Randomized computations [AroraBarak, Ch. 7.1 and 7.3]. Toda's theorem (without proof) [AroraBarak, Thm. 17.14]. BPP is strange [AroraBarak, Ch. 7.5.3]. Sipser-Gacs theorem [AroraBarak, Thm. 7.15].
• Fifth week: Sipser-Gacs theorem cntd. Oracle characterization of BPP (and many other thing for a random oracle): [9]. 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 [10]. Protocol for graph non-isomorphism [AroraBarak, Ch. 8.1.3]. Public coin model is essentially equivalent to the private coin model (without proof) [AroraBarak, Thm 8.12]. IP=PSPACE (with only a high-level sketch of the proof) [AroraBarak, Ch. 8.3]. MIP=NEXP (without proof) [AroraBarak, Ch. 8.5]. Probabilistically Checkable Proofs (PCP) [AroraBarak, Ch. 11.2]. Two disguises of the PCP theorem (with a sketch of one proof) [AroraBarak, Ch. 11.2].
• Sixth week: The monograph [11] is highly recommended source on circuit complexity. Boolean circuits [AroraBarak, Ch. 6.1] or [11, Ch. 1.2]. Shannon counting argument [AroraBarak, Thm. 6.21] or [11, Ch. 1.4]. Nonuniform hierarchy theorem (in more precise form) [AroraBarak, Thm. 6.22] or [11, 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 (without proof) [AroraBarak, Exc. 6.5 and 6.6]. Circuit depth, relations between size and depth, Spira's theorem [11, Ch. 6.1]. NC^k, AC^k and parallel algorithms [AroraBarak, Ch. 6.7]. Branching programs and similar models [AroraBarak, Ch. 14.4.4], [11, Part V] or [12]. The world between NC^1 and NC^2 [13]. Nechiporuk's bound [11, Ch. 6.5 and 15.1].
• Seventh week: Nechiporuk's bound cntd. Rectangular approach to Khrapchenko's bound [11, Ch. 6.7, 6.8]. Lower bounds against AC^0 circuits, random restrictions (high-level idea) [AroraBarak, Ch. 14.1] or [11, Ch. 12]. Lower bounds for monotone circuits, the method of approximations (high-level idea) [AroraBarak, Ch. 14.3] or [11, Ch. 9.10-9.11]. Lower bounds for $AC^0[p]$ circuits (high-level idea) [AroraBarak, Ch. 14.2] or [11, Ch. 12.5-12.6]. A survey on polynomial correlation [14]. Bounded-depth threshold circuits: see [11, Ch. 11.10] or [15] from the perspective of complexity theory, or [16] from the theoretical ML perspective. Lower bound for the majority of thresholds (without proof) [11, Theorem 11.37]. Threshold of majorities (reduction to sign-rank, without proof) [11, Claim 11.40]. Forster's bound on sign-rank (without proof) [17]. Natural Proofs [18] or [AroraBarak, Ch. 23].
• Eighth week: Communication complexity is covered in a great deal of sources: [11, Part 2], [19], [20] or [AroraBarak, Ch. 13]. Combinatorial rectangles and tiling complexity [AroraBarak, Ch. 13.2.2] or [11, Ch. 3.1-3.2]. A separation between tiling complexity and communication complexity, lifting techniques (without proof) [21]. Rank lower bound [AroraBarak, Ch. 13.2.3] or [11, Ch. 4.5]. Log-rank conjecture [AroraBarak, Ch. 13.2.6] or [11, Ch. 4.6]. Non-deterministic communication complexity [11, Ch. 4.2]. Relations between deterministic and non-deterministic complexities [11, Ch. 4.3]. Karchmer-Wigderson games [11, Ch. 3.3]. Private vs. public coins in communication complexity [19], [22]. Rabin-Yao protocol for the equality function [19] or [20, Theorem 5]. Unbounded error probabilistic communication complexity vs. sign-rank [23]. Algebraic complexity [AroraBarak, Ch.16], [24] or [25]. The degree bound (without proof) [24, Sct. 6]. Baur-Strassen Lemma [24, Sct. 7]. Valiant's complexity classes [AroraBarak, Ch. 16.1.4].
• Ninth week: Complexity of univariate polynomials [24, Sct. 9]. Recent advances on matrix multiplication: [26]. Propositional proof complexity (intro): [AroraBarak, Ch. 15] or [9, Part VI] or [27, 28]. I am also trying to maintain a list of open problems that I find important (let me know if you are aware of any developments not accounted for on that page). For connections with practical SAT solving see [29]. For the menagerie of algebraic and geometric proof systems see [30]. Size-width tradeoff for resolution [11, Ch. 18]. Much more information about proof complexity can be also found at the Web page of the topic course I taught last year (and hope to do again at some point in the future).