CMSC 38500-1: Computability and Complexity Theory

Course description. See also the previous version of this course (some changes are anticipated).

Winter 2017: Tuesday, Thursday 10:30am-11:50am (Ry 277)

Office hours: drop by (preferably by appointment).
Homeworks. There will be three homework assignments.

Literature.
1. N. J. Cutland, Computability, Cambridge University Press, 1980.
2. E. Mendelson, Introduction to Mathematical Logic, fifth edition, CRC Press, 2009.
3. M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, third edition, Springer, 2008.
4. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
5. M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
6. F. Eisenbrand, N. Hahnle, A. Razborov, T. Rothvoss, Diameter of Polyhedra: Limits of Abstraction, in Mathematics of Operations Research, Vol. 35, 2010, pages 786 - 794.
7. S. Cook, B. Kapron, A Survey of Classes of Primitive Recursive Functions, 2017.
8. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
9. S. I. Adian, G. S. Makanin, Studies in algorithmic questions of algebra, in Algebra, mathematical logic, number theory, topology, Collection of survey articles. 1. On the occasion of the 50th anniversary of the founding of the Institute, Trudy Mat. Inst. Steklov., 168, 1984, 197-217.
10. H. Hatami, S. Norin, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc., 24 (2011), 547-565.
11. A. Razborov, What is a Flag Algebra?, Notices of the AMS, 60(10): 1324-1327, 2013.
12. A. Nies, Separating classes of groups by first order sentences. International J. of Algebra and Computation, 13, No 3 (2003), 287-302.
13. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
14. A. Razborov, Foundations of computational complexity theory, Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, No. 321, 2005, pages 186-202.
15. S. Cook, Computational Complexity of Higher Type Functions, Proceedings of 1990 Intern. Congress of Mathematicians, Kyoto, Japan, Springer, 1991, 55-69.
16. E. Kushilevitz, N. Nisan, Communication Complexity, Cambridge University Press, 1996.
17. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
18. L. Babai, P. Frankl, J. Simon, Complexity classes in communication complexity theory, in Proceedings of the 27th IEEE FOCS, pages 337-347, 1986.
19. B. Kalyanasundaram, G. Schnitger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, 5(4): 545-557, 1992.
20. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, 106: 385-390, 1992.
21. M. Braverman, Interactive information and coding theory, in Proceedings of The International Congress of Mathematicians, Seoul, 2014, pages 535-559.
22. M. Braverman, A. Garg, D. Pankratov, O. Weinstein, From Information to Exact Communication, 2012.
23. L. Babai, N. Nisan, M. Szegedy, Multiparty protocols, pseudorandom generators for LOGSPACE, and time-space trade-offs, Journal of Computer and System Sciences, 45: 204-232, 1992.
24. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
25. J. Flum, M. Grohe, Parameterized Complexity Theory, Springer-Verlag, 2009.
26. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2013.
Progress and further references.
- First week: Primitive recursive functions [Cutland, Chapters 2.1-2.4; Mendelson, Chapter 3.3]. The Ackermann function [Cut., Ch.2, Example 5.5], see also Wikipedia article. The latter contains our computation of A(4,3) as well as a few other values. Lower envelopes and Davenport-Schinzel sequences [5, Section 1.1]. Upper bounds on the length of DS-sequences of order 3 [5, Section 2.2]. Another geometric context in which a similar stuff with intervals, symbols etc. appears is the combinatorial approach to the Hirsh conjecture [6]. The Ackermann function is not primitive recursive. A finer hierarchy within the class of primitive recursive functions 50 years after [7].
- Second week: Recursive functions [Cut., Ch. 3.2 and 2.5; Mend., Ch. 3.3]. Turing machines [Mend., Ch. 5.1; Cut., Ch. 3.4]. Unlimited register machines [Cut., Ch. 1 and 2]. Every recursive function is URM-computable [Cut., Theorem 3.2.2]. Markov Normal Algorithms [Mend., Ch. 5.5; Cut., Ch. 3.5]. Church-Turing Thesis [Cut., Ch. 3.7]. Decidable problems, recursive and recursively enumerable sets [Cut., Ch. 6 and 7]. Enumerations $\phi_e$ and $W_e$ of recursive functions and r.e. sets [Cut., Ch. 4.2]. Halting problem is undecidable [Cut., Thm 6.1.3]. Many-one reducibility [Cut., Ch. 9.1].
- Third week: Many-one reducibility cntd. s-m-n Theorem [Cut., Ch. 4.4]. Rice's theorem [Cut., Thm 6.1.7]. Relative (oracle) computations: [Cut., Ch. 9.4]. Turing equivalence and degrees [Cut., Ch. 9.5]. Post's problem: [Cut., Problem 9.5.11]. Simple sets [Cut., Ch. 7.4]. Creative sets [Cut., Ch. 7.3]. Creative sets are not simple [Cut., Thm 7.3.11]. Effective (recursive) operators and their simple properties: [Cut., Ch. 10.1]. Myhill-Shepherdson theorem [Cut., Ch. 10.2].
- Fourth week (short): Myhill-Shepherdson cntd. Kleene's fixed point theorem (aka the First Recursion Theorem) [Cut., Ch. 10.3]. First-order logic [Mend., Ch. 2; Cut., Ch. 8.1].
- Fifth week: Peano Arithmetic [Mend., Ch. 3.1]. Defining new function symbols [Mend., Ch. 2.9]. Recursive functions are definable (representable) in PA [Mend., Proposition 3.24]. $\omega$-consistency [Cut., Ch. 8.3; Mend., Ch, 3.5]. Th(PA) is undecidable [Cut., Ch. 8.3; Mend., Ch. 3.6]. There are a few variations on the topic "Goedel Incompleteness Theorem via recursion theory". The simple version we did in the class more or less corresponds to [Mend., Prop. 3.47 and Corollary 3.48]. I recommend to check out also [Cut., Theorem 8.2.4] in which the Incompleteness Theorem is handled without any technical work on definability/arithmetization whatsoever. [8] is an excellent survey on decidable theories. Quantifier elimination technique [Mend., page 110 (Ch. 2.12)]. For Presburger Arithmetic see the Wikipedia article which also gives a reference to the simple QE proof we did in class. Another beautiful proof based on totally different ideas can be found in [8, Sct. 3.4]. Among other things, it also conclusively demonstrates that second-order systems sometimes are useful. Robinson's Arithmetic, called RR in [Mend., Ch. 3.4]. Deduction Theorem [Mend., Ch. 2.4, Prop. 2.5]. Pure first-order calculus is undecidable [Mend., Ch. 3.6, Cor. 3.52]. Hilbert's Tenth problem [Cut., Ch. 6.3 and 6.6.]. Word problem in groups [Cut., Ch. 6.2]; for more information see [9]. Asymptotic extremal combinatorics is undecidable [10]; for the context see [11]. Regarding Taylor's question (the theory of all groups vs. the theory of finitely presented groups), I have discovered the reference [12]. It answers (quite non-trivially) this question as well as many of its natural variations.
- Sixth week: Our basic text on Kolmogorov Complexity is [LiVitanyi], but some simple things are covered in [13, Chapter 6.4]. Invariance Theorem [13, Thm. 6.27]. Incompressible strings [13, Def. 6.28, Thm. 6.29-6.32]. Conditional Kolmogorov complexity [LiVitanyi, Def. 2.1.1 and 2.1.2]. Algorithmic Prefix Complexity (just mentioned) [LiVitanyi, Ch. 3]. Classical information theory [LiVitanyi, Ch. 1.11]. Conditional Kolmogorov complexity behaves as expected [LiVitanyi, Thm. 2.8.2]. Random infinite sequences [LiVitanyi, Ch. 2.5.2]. Incompressibility of finite prefixes i.o. implies randomness (without proof) [LiVitanyi, Thm. 2.5.5].
- Seventh week: For a highly informal introduction into the complexity block see e.g. [14]. Machine-independent complexity, Blum's axioms [Cut., Ch. 12.1]. Speed-up Theorem (without proof) [Cut., Thm. 12.2.1]. Gap Theorem (without proof) [Cut., Thm. 12.3.1]. Complexity classes, DTIME [13, Ch. 7.1; AroraBarak, Ch. 1.6]. Time Hierarchy Theorem [13, Thm. 9.10; AroraBarak, Thm. 3.1]. Space Hierarchy Theorem (without proof) [13, Thm. 9.3]. Relations between time and space [AroraBarak, Thm. 4.2]. Complexity of decidable logical theories [8, Ch. 4]. Class P [AroraBarak, Ch. 1.6]. Strong Church-Turing thesis [AroraBarak, Ch. 1.6]. Discussion on worst-case analysis, asymptotic assumptions etc., see e,g, [14; 15; 13, Ch. 7.2; AroraBarak, Ch. 1.6]. Karp reductions [AroraBarak, Ch. 2.2]. Class NP [AroraBarak, Ch. 2.1]. NTIME and equivalence of the two definitions [AroraBarak, Ch. 2.1.1]. Universal NP-complete problem [AroraBarak, Thm. 2.9]. Cook-Levin Theorem [13, Thm. 7.37].
- Eighth week: guest lectures by Prof. Babai. The standard text on communication complexity is [16]; for a high-level introduction see [17]. Communication protocol, communication complexity [16, Ch. 1.1]. Combinatorial rectangles [16, Ch 1.2]. Lower bound via rectangle covers [16, Cor. 1.17]. Mehlhorn-Schmidt rank lower bound [16, Lem. 1.28]. Complexity of the Equality function. Lovasz-Saks "Log-rank conjecture". Randomized complexity [16, Ch. 3]. Private vs. public coin. Private-coin protocol for Equality with complexity O(log n) (sketch). Distributional complexity [16, Ch. 3.4]. Characterization of randomized public-coin complexity in terms of distributional complexity [16, Thm. 3.20], connections to game theory. The Disjointness function [18]. The $\Omega(n)$ lower bound on the randomized complexity of Disjointness (sketch) [19,20]. Informational complexity (mentioned) [21]. Refined bounds for Disjointness (mentioned) [22]. Discrepancy of hypergraphs. Discrepancy w.r.to system of combinatorial rectangles [16, Ch. 3.5]. Lower bound on distributional complexity in terms of discrepancy [16, Prop. 3.28]. Hadamard Matrices. Discrepancy of Hadamard matrices and lower bound for the randomized complexity of Inner Product [16, Example 3.29]. Multiparty communication complexity: the Number on Forehead (NOF) model [16, Ch. 6]. Lower bounds for the Inner Product and the Quadratic Character functions (sketch) [23].
- Ninth week: Prof. Babai cntd. Applications of multiparty communication complexity to the multi-head one-way space complexity [23]. Turing complexity resumed: Cook-Levin Theorem cntd. Examples of NP-complete problems [24; 13, 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 [24, Sct. 4.2], parameterized complexity [25] and approximation algorithms [26]. TQBF and its PSPACE-completeness [AroraBarak, Thm. 4.13].
- Tenth week (short): TQBF is PSPACE-complete cntd. Savitch's theorem [AroraBarak, Ch. 4.2.1]. Other complete problems for PSPACE and EXPTIME with references can be found here and here. 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].