CMSC 38700-1: Complexity Theory B

Course description

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

Office hours: by appointment.

Homeworks. There will be three homework assignments.

Literature.
1. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
2. O. Reingold, Undirected connectivity in log-space, Journal of the ACM, 55(4): 17:1-17:24 (2008).
3. M. Saks, S. Zhou, BP HSpace(S) subseteq DSPACE(S3/2), J. Comput. Syst. Sci., 58(2): 376-403 (1999).
4. O. Reingold, L. Trevisan, S. Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem, STOC 2006: 457-466.
5. S, Jukna, Complexity of Boolean functions, Springer-Verlag, 2012.
6. 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.
7. 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.
8. A. Potechin, Bounds on monotone switching networks for directed connectivity, in Proc. 51st FOCS, pp. 553--562. IEEE Comp. Soc. Press, 2010.
9. I. Dinur, The PCP theorem by gap amplification, in Proc. 38th STOC, pp. 241-250, 2006.
10. J. Radhakrishnan, M.Sudan, On Dinur's proof of the PCP theorem, Bull. Amer. Math. Soc., 44 (2007), 19-61.
11. A. Drucker, Building Assignment Testers. Expository note.
12. E. Viola, Correlation bounds for polynomials over {0,1}, ACM SIGACT News, 40(1), 2009.
13. A. Razborov, Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity, Combinatorica, Vol. 10, No 1, 1990, pages 81-93.
14. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
15. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, Springer-Verlag, 2011.
16. M. Goos, T. Pitassi, T. Watson, Deterministic Communication vs. Partition Number, 2015.
17. B. Chazelle, The discrepancy method, Cambridge University Press, 2002.
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. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4): 612-625, 2002.
20. H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288(1):21-43, 2002.
21. A. Razborov, Lecture notes of the Course on Quantum Computing.
22. P. Hatamii, R. Kulkarni and D. Pankratov. Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys Number 4 (2011) pp. 1-27.
23. R. O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014.
24. S. Chakraborty, R. Kulkarni, V. Satyanarayana, S. Lokam, N. Saurabh, Upper Bounds on Fourier Entropy, in International Computing and Combinatorics Conference COCOON 2015: Computing and Combinatorics, pp 771-782.
25. V. Strassen, Algebraic Complexity Theory, Chapter 11 of Handbooks of Theoretical Computer Science, Volume A (Algorithms and Complexity), 1990.
26. 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.
27. A. Razborov, Proof Complexity and Beyond, SIGACT News, 47(2):66-86, 2016.
28. A. Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution, Annals of Mathematics, Vol. 181, No 2, 2015, pages 415-472.
29. J. Krajicek, P. Pudlak, Some consequences of cryptographical conjectures for S_2^1 and EF, Information and Computation, vol. 140 (1998), no. 1, pp. 82-94.
30. A, Razborov, Lecture notes of the Course on Propositional Proof Complexity, 2009-2014.
31. Jakob Nordstrom, Pebble Games, Proof Complexity, and Time-Space Trade-offs, Logical Methods in Computer Science, volume 9, issue 3, article 15, 2013.
32. N. Fleming, D. Pankratov, T. Pitassi, R. Robere, Random CNFs are Hard for Cutting Planes Contact, 2017.
33. D. Grigoriev, E. Hirsch, D. Pasechnik, Complexity of semi-algebraic proofs, Moscow Mathematical Journal, 2(4):647-679, 2002.
34. B. Barak, D. Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, In Proceedings of International Congress of Mathematicians (ICM) , volume IV, pages 509-533, 2014.
35. J. Lee, P. Raghavendra, D. Steurer, Lower bounds on the size of semidefinite programming relaxations, In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 567-576, 2015.
36. S. Buss, D. Grigoriev, R. Impagliazzo, T. Pitassi, Linear gaps between degrees for the Polynomial Calculus modulo distinct primes, Journal of Computer and System Sciences, 62:267-289, 2001.
37. D. Grigoriev, Linear lower bounds on degrees of Postivestellensatz calculus proofs for the parity, Theoretical Computer Science, 259:613-622, 2001.
38. O. Prosorov, Sheaf-Theoretic Formal Semantics.
39. M. Kuhlmann, Dependency Structures and Lexicalized Grammars, 2007.

Progress and references. Prequel to this course (sort of). I will try to make it as self-contained as possible.
- First week: Uniform and non-uniform models of computation (a general discussion). Randomized computations [AroraBarak, Ch. 7.1 and 7.3]. BPP is strange [AB, Ch. 7.5.3]. Error-reduction [AB, Thm. 7.10]. $BPP\subseteq \Sigma_2^p$ [AB, Thm. 7.15]. Sub-linear space, classes L, RL and NL [AB, Ch. 4.1]. Log-space reductions, STCONN (called PATH in the book) is NL-complete [AB, Ch. 4.3]. Immerman-Szelepcsenyi theorem [AB, Thm. 4.20]. USTCONN is in L (without proof) [2]. Towards L=RL (or NL): [3,4]. [5] is highly recommended source on circuit complexity. Boolean circuits [AB, Ch. 6.1; 5, Ch. 1.2]. Shannon counting argument [AB, Thm. 6.21; 5, Ch. 1.4]. Nonuniform hierarchy theorem [AB, Thm. 6.22; 5, Thm. 1.19].
- Second week: Advice Turing machines and an alternate description of P/poly [AB, Ch. 6.3]. BPP is in P/poly [AB, Thm. 7.14]. Meyer's theorem (without proof) [AB, Thm. 6.20]. Karp-Lipton theorem (without proof) [AB, Thm. 6.19]. Kannan's theorem [AB, Exc. 6.5 and 6.6]. Lower bounds for general circuits [5, Ch. 1.6; 6]. Boolean formulas [AB, Ch. 1.4; 5, Ch. 6]. Circuit depth, relation to the formula size [5, Ch. 6.1]. Classes NC and AC [AB, Ch. 6.7.1]. Branching programs and other space-oriented models [AB, Ch. 14.4.4; 5, Part V]; for a concise survey see [7]. mon-SL \neq mon-NL (without proof) [8]. Khrapchenko's bound [5, Ch. 6.8], preceding and following developments [5, Ch. 6.2, 6.3]. Nechiporuk's bound [5, Ch. 6.5 and 15.1]. Lower bounds against AC^0 circuits (general overview) [AB, Ch. 14.1; 5, Ch. 12].
- Third week: guest lectures (Professor Drucker). Dinur's alternative (combinatorial) proof of the PCP Theorem [9,10,11].
- Fourth week: Monotone circuits lower bounds (without proof) [AB, Ch. 14.3; 5, Ch. 9.10-9.11]. Lower bounds for $ACC^0[p]$ [AB, Ch. 14.2; 5, Ch. 12.5-12.6]. A survey on polynomial correlation [12]. A simple lower bound for monotone formulas [13; 5, Ch. 7.1-7.3]. Communication complexity is covered in a great deal of sources: [14; 15; AB, Ch. 13; 5, Part 2]. Combinatorial rectangles and tiling complexity [AB, Ch. 13.2.2; 5, Ch. 3.1-3.2]. A separation between tiling complexity and communication complexity (without proof) [16]. Rank lower bound [AB, Ch. 13.2.3; 5, Ch. 4.5]. Log-rank conjecture [AB, Ch. 13.2.6; 5, Ch. 4.6]. Non-deterministic communication complexity [5, Ch. 4.2]. A relation between deterministic and non-deterministic complexities [5, Ch. 4.3].
- Fifth week: Karchmer-Raz-Wigderson approach to monotone depth (without proofs): [AB, Ch. 14.5; 5, Ch. 3.3, 7.4-7.6]. Multi-party communication complexity [AB, Ch. 13.3; 5, Ch. 5.4]. Discrepancy bound [AB, Ch. 13.2.4; 5, Ch. 5.5], and the discrepancy method in general [17]. Babai-Nisan-Szegedy bound (without proof) [AB, Th. 13.24; 5, Ch. 5.6]. Majority and threshold circuits [18; 5, Ch. 11.10]. Lower bounds for depth-three circuits with small bottom fan-in [5, Thm. 11.43-11.44]. Forster's bound [19]. Matrix rigidity [5, Ch. 12.8]. Natural proofs [AB, Ch. 23]. Pseudorandom function generators [AB, Ch. 9.5.1]. Goldreich-Goldwasser-Micali construction [AB, Thm 9.17]. Polynomial correlation bounds via Gowers norms [12, pages 9-10].
- Sixth week: Polynomial correlation bounds cntd. Polynomial degree, approximate polynomial degree, decision tree complexity, certificate complexity and block-sensitivity [20; 21, Sct. 6.2]. The Sensitivity Conjecture [22]. A standard book on the (Fourier) analysis of Boolean functions is [23]; what we have done so far roughly corresponds to [23, Ch. 1.2-1.5]. The convolution formula [23, Thm. 1.27].
- Seventh week: The convolution formula (proof). Influence, total influence and average sensitivity [23, Ch. 2.2-2.3]. [24] is the most recent paper on the Entropy/Influence conjecture I am aware of. The linearity test [23, Ch. 1.6]. Algebraic complexity [25; AB, Ch.16]. The degree bound (without proof) [25, Sct. 6]. Baur-Strassen Lemma [25, Sct. 7]. Bilinear complexity [25, Sct. 10]. The group-theoretic approach to matrix multiplication [26]. Valiant's complexity classes [AB, Ch. 16.1.4].
- Eighth week: Valiant's complexity classes cntd. For an informal introduction to proof complexity see my essay [27], and for the specific project of obtaining conditional lower bounds for strong proof systems see the introduction section in [28]. No feasible interpolation for EF if RSA is secure [29]. Width-size relation and exponential lower bounds for resolution [5, Ch. 18; 30, Sct. 2]; for earlier methods see [AB, Ch. 15.2.1].
- Ninth week: width-size relation cntd. For a comprehensive survey on space complexity see [31]. An excellent treatment of Cutting Planes [5, Ch. 19]. Rank lower bounds for independence number in graphs (without proof) [5, Thm. 19.32]. Feasible interpolation for cutting planes [5, Ch. 19.4; 30, Sct. 7.2.1]. Lower bounds for the Clique-Coloring principle [5, Ch. 19.4.1]; for the recent development see [32]. An early (but still relevant!) survey of semi-algebraic proof systems [33]. Some reading on applications of Sum-of-Squares (the landscape is changing very rapidly!) [34,35]. Lower bound for Tseitin tautologies [36,37].
- Tenth week: SoS lower bound for Tseitin tautologies cntd. Space lower bound for the Pigeon-Hole-Principle [30, Sct. A3]. Project (Robert Green). Sheaf-theoretic semantics; linking Discourse Representation Theory to techniques used in topology [38]. We view elements of discourse as "incomplete semantic pictures", and sheaf theory provides a very natural description of the phenomenon of the way that discourse builds up a global semantic picture. Building Discourse Representation Structures in Python. Brief discussion of dependency structures: grammars are typically viewed as generators of strings and parse trees, but they also generate dependency structures. The general spirit is that nice projectivity properties (subtrees project to complete intervals) correspond to easy parsing. Studying dependency structures (and the way that they project) gives us nice algorithms for parsing languages of varying degrees of context sensitivity. [39] is an excellent exposition to the subject and its applications.