MATH/CMSC 38800: Complexity Theory

Spring 2019: Tuesday, Thursday 9:30am-10:50am (Eck 202)

Office hours: drop by (preferably by appointment) or ask your question on Piazza.

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. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
5. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
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, Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity, Combinatorica, Vol. 10, No 1, 1990, pages 81-93.
15. S. Cook, T. Pitassi, R. Robere, B. Rossman, Exponential Lower Bounds for Monotone Span Programs, 2016.
16. E. Viola, Correlation bounds for polynomials over {0,1}, in ACM SIGACT News, 40(1), 2009.
17. A. Razborov, On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52.
18. R. Bhatia, Matrix Analysis, Springer-Verlag, 1997.
19. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, in Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
20. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
21. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
22. M. Goos, T. Pitassi, T. Watson, Deterministic Communication vs. Partition Number, 2015.
23. A. Garg, M. Goos, P. Kamath, D. Sokolov, Monotone Circuit Lower Bounds from Resolution, 2017 (also STOC 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. H. Cohn, R. Kleinberg, B. Szegedy, C. Umans, Group-theoretic algorithms for matrix multiplication, Foundations of Computer Science. 46th Annual IEEE Symposium, 2005, pages 379-388.
28. A. Razborov, Proof Complexity and Beyond, SIGACT News, 47(2):66-86, 2016.
29. A, Razborov, Lecture notes of the Course on Propositional Proof Complexity, 2009-2014.

Progress and references. Our main reference is [1] (referred hereafter as AroraBarak); 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; 4, Ch. 7.1]. Time Hierarchy Theorem [AroraBarak, Thm. 3.1; 4, Thm. 9.10]. Space Hierarchy Theorem (without proof) [4, Thm. 9.3]. Relations between time and space [AroraBarak, Thm. 4.2]. Complexity of decidable logical theories [5, Ch. 4]. Class P [AroraBarak, Ch. 1.6]. Strong Church-Turing thesis [AroraBarak, Ch. 1.6]. Discussion on worst-case analysis, asymptotic assumptions etc. [AroraBarak, Ch. 1.6; 4, Ch. 7.2; 2]. Karp (many-one) reductions [AroraBarak, Ch. 2.2]. Class NP [AroraBarak, Ch. 2.1]. NTIME and equivalence of the two definitions [AroraBarak, Ch. 2.1.1].
- Second week: Universal NP-complete problem [AroraBarak, Thm. 2.9]. Cook-Levin Theorem [4, Thm. 7.37]. Examples of NP-complete problems [6; 4, Ch. 7.5; AroraBarak, Ch. 2.4], see also Wikipedia article. Further reading on relevant topics that were briefly mentioned in class: pseudo-polynomial algorithms [6, Sct. 4.2], approximation algorithms [7]. For basic facts about Vertex Cover see Wikipedia article.
- Third week: Vertex Cover cntd. TQBF and its PSPACE-completeness [AroraBarak, Thm. 4.13]. Savitch's theorem [AroraBarak, Ch. 4.2.1]. Other complete problems for PSPACE and EXPTIME with references can be found here and here. For that matter, this is the Complexity Zoo (how many of those classes can you name?) Ladner's theorem (without proof) [AroraBarak, Ch. 3.3]. Limits of diagonalization: Baker-Gill-Solovay theorem [AroraBarak, Thm. 3.7]. Polynomial-time hierarchy [AroraBarak, Ch. 5]. Sub-linear space, classes L and NL [AroraBarak, Ch. 4.1]. Immerman-Szelepcsenyi theorem (without proof) [AroraBarak, Thm. 4.20]. Log-space reductions, STCONN (called PATH in the book) is NL-complete [AroraBarak, Ch. 4.3]. Horn satisfiability is P-complete.
- Fourth week: Horn satisfiability cntd. 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]. Protocol for graph non-isomorphism [AroraBarak, Ch. 8.1.3]. Quantifier representation of AM [AroraBarak, Figure 8.2]. AM collapses for finitely many rounds [8]. Public coin model is equivalent to the private one (without proof) [AroraBarak, Thm 8.12]. IP=PSPACE (without proof) [AroraBarak, Ch. 8.3]. MIP=NEXP (without proof) [AroraBarak, Ch. 8.5]. Probabilistically Checkable Proofs (PCP) [AroraBarak, Ch. 11.2].
- Fifth week: two disguises of the PCP theorem (without ptoof) [AroraBarak, Ch. 11.2]. [9] is highly recommended source on circuit complexity. Boolean circuits and formulas [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]. Circuit depth, relations between size and depth, Spira's theorem [9, Ch. 6.1]. Branching programs and other space-oriented models [AroraBarak, Ch. 14.4.4; 9, Part V; 10]. The world between NC^1 and NC^2 [11].
- Sixth week: the Proof Week (guest lectures by Aaron Potechin). Immerman-Szelepcsenyi theorem. #P is in IP. IP=PSPACE. Equivalence of two views of the PCP theorem. Ladner's theorem.
- Seventh week: Linear lower bounds for general circuits (without 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 (without proof) [AB, Ch. 14.1; 9, Ch. 12]. Lower bounds for monotone circuits (without proof) [AB, Ch. 14.3; 9, Ch. 9.10-9.11]. Karchmer-Raz-Wigderson approach to monotone depth (without proof) [AB, Ch. 14.5; 9, Ch. 3.3, 7.4-7.6]. Lower bounds for monotone formulas based on the rank technique [14; 9, Ch. 7.1-7.3]. Recent applications [15]. Lower bounds for $AC^0[p]$ circuits [AB, Ch. 14.2; 9, Ch. 12.5-12.6]. A survey on polynomial correlation [16]. Bounded-depth threshold circuits [9, Ch. 11.10; 17].
- Eighth week: Bounded-depth threshold circuits cntd. Lower bound for the majority of thresholds [9, Theorem 11.37]. Threshold of majorities, part 1 (reduction to the sign-rank) [9, Claim 11.40]. Ad hoc proof of Forster's bound (skipping the same essential step as ours) [9, Theorem 4.42]. All the material on matrix norms can be found in [18]; it is also summarized (and used in a very similar context) in [19]. Communication complexity is covered in a great deal of sources: [20; 21; 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) [22]. [23] is one of their latest applications, see also the literature therein. 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 [20; 24]. Rabin-Yao protocol for the equality function [20; 21, Theorem 5].
- Ninth week: Rabin-Yao protocol cntd. Unbounded error probabilistic communication complexity vs. sign-rank [25]. Natural proofs [AroraBarak, Ch. 23]. Pseudorandom function generators [AroraBarak, Ch. 9.5.1]. Goldreich-Goldwasser-Micali construction [AroraBarak, Thm. 9.17]. Algebraic complexity [26; AroraBarak, Ch.16]. The degree bound (without proof) [26, Sct. 6]. Baur-Strassen Lemma [26, Sct. 7]. Bilinear complexity [26, Sct. 10]. The group-theoretic approach to matrix multiplication [27].
- Tenth week: Valiant's complexity classes [AroraBarak, Ch. 16.1.4]. Propositional proof complexity: [AroraBarak, Ch. 15; 9, Part VI; 28, 29]. Width-size relation and exponential lower bounds for resolution [9, Ch. 18; 29, Sct. 2]; for earlier methods see [AroraBarak, Ch. 15.2.1].