MATH/CMSC 38800: Complexity Theory

Spring 2021: Tuesday, Thursday 9:40am-11am (Zoom)

Office hours: by appointment (I will try to offer them privately but can not guarantee it); if you ask a question on Ed Discussion, it will be answered promptly.

Homeworks. There will be three homework assignments.

Literature.
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. N. J. Cutland, Computability, Cambridge University Press, 1980.
4. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
5. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
6. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
7. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2013.
8. 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.
9. S, Jukna, Complexity of Boolean functions, Springer-Verlag, 2012.
10. 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.
11. S. Cook, A Taxonomy of Problems with Fast Parallel Algorithms, in Information and Control, 64: 2-22, 1985.
12. K.Iwama, O.Lachish, H.Morizumi, R.Raz, An Explicit Lower Bound of 5n - o(n) for Boolean Circuits, in Proceeding of the 33rd Symposium on the Theory of Computing, 2001, pp. 399-408.
13. M. Find, A. Golovnev, E. Hirsch, A. Kulikov. A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function, Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). IEEE Computer Society, pp. 89--98, 2016.
14. A. Razborov, On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52.
15. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4): 612-625, 2002.
16. E. Viola, Correlation bounds for polynomials over {0,1}, in ACM SIGACT News, 40(1), 2009.
17. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
18. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
19. M. Goos, T. Pitassi, T. Watson, Deterministic Communication vs. Partition Number, 2015.
20. I. Newman, Private vs. common random bits in communication complexity, in Information Processing Letters, 39(2), 67-71, 1991.
21. R. Paturi, J. Simon, Probabilistic Communication Complexity, in Journal Of Computer And System Sciences , 33, 106-123, 1986.
22. V. Strassen, Algebraic Complexity Theory, Chapter 11 of Handbooks of Theoretical Computer Science, Volume A (Algorithms and Complexity), 1990.
23. 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.
24. J. Alman, V. Vassilevska-Williams, A Refined Laser Method and Faster Matrix Multiplication, 2020.
25. A. Razborov, Proof Complexity and Beyond, SIGACT News, 47(2):66-86, 2016.
26. J. Krajicek, Proof Complexity, Cambridge University Press, 2019.
27. A. Razborov, Lecture notes of the Course on Propositional Proof Complexity, 2009-2014.
Progress and references. Our main reference is [1] (referred to as [AroraBarak] hereafter); others will be added here as we are making progress.
- First week: For a highly informal introduction into classical Turing complexity see [2]. Machine-independent complexity, Blum's axioms [3, Ch. 12.1]. Speed-up Theorem (without proof) [3, Thm. 12.2.1]. Gap Theorem (without proof) [3, Thm. 12.3.1]. Complexity classes, DTIME [AroraBarak, Ch. 1.6; 5, Ch. 7.1]. Time Hierarchy Theorem [AroraBarak, Thm. 3.1; 5, Thm. 9.10]. Implementation of the Universal Turing Machne, with many meticulous details [AroraBarak, Sct. 1.7]. Complexity of decidable logical theories [4, Ch. 4]. Oracle Turing machines [AroraBarak, Sct. 3.4] and Cook reductions [AroraBarak, Exerc. 2.14]. Karp (many-one) reductions [AroraBarak, Ch. 2.2].
- Second week: Strong Church-Turing thesis [AroraBarak, Ch. 1.6]. Discussion on worst-case analysis, asymptotic assumptions etc. [AroraBarak, Ch. 1.6; 5, Ch. 7.2; 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.1] and the equivalence of two definitions [AroraBarak, Thm. 2.6]. 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; 5, Ch. 7.5; AroraBarak, Ch. 2.4], see also Wikipedia article. Levin reductions [AroraBarak, Sct. 2.3.6].
- Third week: Examples of NP-complete problems cntd. Further reading on relevant topics that were briefly mentioned in class: pseudo-polynomial algorithms [6, Sct. 4.2], approximation algorithms [7]. Ladner's theorem (without proof) [AroraBarak, Ch. 3.3]. TQBF and its PSPACE-completeness [AroraBarak, Thm. 4.13]. Savitch's theorem [AroraBarak, Ch. 4.2.1]. 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].
- Fourth week: Polynomial-time hierarchy cntd. [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]. BPP is strange [AroraBarak, Ch. 7.5.3]. Error-reduction [AroraBarak, Thm. 7.10]. $BPP\subseteq \Sigma_2^p$ [AroraBarak, Thm. 7.15]. Deterministic interactive proofs [AroraBarak, Ch. 8.1.1]. Interactive proofs [AroraBarak, Ch. 8.1]. Quantifier representation of AM [AroraBarak, Figure 8.2].
- Fifth week: AM collapses for finitely many rounds [8]. Protocol for graph non-isomorphism [AroraBarak, Ch. 8.1.3]. Public coin model is equivalent to the private one (without proof) [AroraBarak, Thm 8.12]. IP=PSPACE (with 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 (without proofs) [AroraBarak, Ch. 11.2]. The monograph [9] is highly recommended source on circuit complexity. Boolean circuits [AroraBarak, Ch. 6.1; 9, Ch. 1.2]. Shannon counting argument [AroraBarak, Thm. 6.21; 9, Ch. 1.4]. Nonuniform hierarchy theorem [AroraBarak, Thm. 6.22; 9, 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]. Meyer's theorem (without proof) [AroraBarak, Thm. 6.20]. Karp-Lipton theorem (without proof) [AroraBarak, Thm. 6.19]. Kannan's theorem [AroraBarak, Exc. 6.5 and 6.6].
- Sixth week: Kannan's theorem cntd. Circuit depth, relations between size and depth, Spira's theorem [9, Ch. 6.1]. Branching programs [AroraBarak, Ch. 14.4.4; 9, Part V; 10]. The world between NC^1 and NC^2 [11]. Linear lower bounds for general circuits (with high-level idea of the proof) [12,13]. Nechiporuk's bound [9, Ch. 6.5 and 15.1]. Rectangular approach to Khrapchenko's bound [9, Ch. 6.7, 6.8]. Lower bounds against AC^0 circuits, random restrictions (high-level ideas) [AroraBarak, Ch. 14.1; 9, Ch. 12]. Lower bounds for monotone circuits, the method of approximations (high-level ideas) [AroraBarak, Ch. 14.3; 9, Ch. 9.10-9.11]. Lower bounds for $AC^0[p]$ circuits (the first half of the proof) [AroraBarak, Ch. 14.2; 9, Ch. 12.5-12.6].
- Seventh week: Lower bounds for $AC^0[p]$ circuits cntd. Bounded-depth threshold circuits [9, Ch. 11.10; 14]. Lower bound for the majority of thresholds (high-level idea) [9, Theorem 11.37]. Threshold of majorities (reduction to sign-rank) [9, Claim 11.40]. Forster's bound on sign-rank (without proof) [15]. A survey on polynomial correlation [16]. Communication complexity is covered in a great deal of sources: [17; 18; AroraBarak, Ch. 13; 9, Part 2]. Combinatorial rectangles and tiling complexity [AroraBarak, Ch. 13.2.2; 9, Ch. 3.1-3.2]. A separation between tiling complexity and communication complexity, lifting techniques (without proof) [19]. Rank lower bound [AroraBarak, Ch. 13.2.3; 9, Ch. 4.5]. Log-rank conjecture [AroraBarak, Ch. 13.2.6; 9, Ch. 4.6]. Non-deterministic communication complexity [9, Ch. 4.2]. Relations between deterministic and non-deterministic complexities [9, Ch. 4.3]. Private vs. public coins in communication complexity [17; 20]. Rabin-Yao protocol for the equality function [17; 18, Theorem 5].
- Eighth week: Unbounded error probabilistic communication complexity vs. sign-rank [21]. Algebraic complexity [AroraBarak, Ch.16; 22; 23]. The degree bound (without proof) [22, Sct. 6]. Baur-Strassen Lemma [22, Sct. 7]. Bilinear complexity [22, Sct. 10]. Recent advances on matrix multiplication: [24]. Valiant's complexity classes [AroraBarak, Ch. 16.1.4]. Propositional proof complexity (intro): [AroraBarak, Ch. 15; 9, Part VI; 25; 26; 27].
- Ninth week: Introduction into proof complexity cntd. Width-size relation and exponential lower bounds for resolution [9, Ch. 18; 27, Sct. 2]; for earlier methods see [AroraBarak, Ch. 15.2.1]. Feasible interpolation (framework) [26, Ch. 17]. Lower bounds for cutting planes using feasible interpolation [9, Ch. 19.4; 26, Ch. 18.1].