## CMSC 38700-1: Complexity Theory B

Course description

Spring 2010: Tuesday, Thursday 1:30pm-2:50pm (Ry 277)
• Office hours: by appointment.

• Homeworks. There will be three homework assignments. You are encouraged to work together on solving homework problems. All students must turn in their own write-up of the solutions. If you work with other people, you must put their names clearly on the write-up.
• Progress and references. Prequel to this course. I will try to make it as self-contained as possible, though.

All references are to the book by Arora and Barak [1], unless stated otherwise. Many of the sources listed below can be used for further reading on some of the topics only briefly touched in the classroom. If I promised a reference in class and then forgot about it please remind me.

• First week: Boolean circuits [Ch. 6.1]. Shannon counting argument [Thm. 6.21]. Nonuniform hierarchy theorem [Thm. 6.22]. Advice Turing machines and an alternate description of P/poly [Ch. 6.3]. BPP is in P/poly [Thm. 7.14]. Karp-Lipton Theorem [Thm. 6.19]. \$\Sigma_2^p\$ does not have small circuits [Exc. 6.5 and 6.6], see also this recent post pertained to the discussion we had in class. Circuit depth, \$NC^k\$ etc. [Ch. 6.7.1], for a comprehensive survey of related complexity classes see [2]. Complete bases [3, Ch. 1.3]. Boolean formulas [3, Ch. 1.4]. Relations between circuit size, formula size and depth [3, Ch.7]. Khrapchenko's bound [3, Ch. 8.8]; our exposition follows ideas from [4,5].
• Second week: Khrapchenko's bound cntd. Sub-linear space, classes L and NL [Ch. 4.1]. Uniform families of circuits [Ch. 6.2]. Branching programs [Ch. 14.4.4]. For a comprehensive survey of related models see [6]. USTCONN in logarithmic space (without proof) [7]. Nechiporuk's bound [3, Ch. 14.3]. Immerman-Szelepcsenyi theorem [Thm. 4.20]; our proof follows the exposition in [8, Ch. 8.6]. Lower bounds for \$AC^0\$ [Ch. 14.1].
• Third week (short): Lower bounds for \$AC^0\$ cntd. Applications to the Fourier analysis [9]. Small restrictions switching lemma [10]. Motivations for the "constructive" proof of the switching lemma can be found in [11, Appendix], and another exposition is in [12]. Monotone circuits lower bounds (without proof) [Ch. 14.3].
• Fourth week: Lower bounds for \$ACC^0\$ [Ch. 14.2]; our version closely follows one of the original papers [13]. A survey on polynomial correlations: [14]. Barrington's theorem [15]. Non-uniform automata over other groups: [16]. Communication complexity [Ch. 13.1]; a comprehensive reference on the subject is [17], see also [24]. Combinatorial rectangles and tiling complexity [Ch. 13.2.2].
• Fifth week: Rank lower bound [Ch. 13.2.3]. Log-rank conjecture [Ch. 13.2.6]. Non-deterministic communication complexity [17, Ch. 2.1]. The relation between deterministic and non-deterministic complexities [17, Ch. 2.3]. Quadratic separation between them [17, Example 2.12]. Application to circuit complexity (simple lower bound for MAXIMAL COVER) and Karchmer-Raz-Wigderson approach (without proofs) [17, Ch. 10]; see also the original papers [4,18,19]. Multi-party communication complexity [Ch. 13.3]. Discrepancy [Ch. 13.2.4]. Babai-Nisan-Szegedy bound [Th. 13.24]. Gowers's exposition of hypergraph regularity lemma [20].
• Sixth week: BNS bound cntd. Majority and threshold circuits [21]. ACC^0 vs. depth-3 majority circuits (without proof) [22]. Forster's bound for unbounded error communication complexity (without proof) [23]. One-way functions [Ch. 9.2.1]. Pseudo-random generators [Ch. 9.2.3]. All polynomially bounded stretches are equivalent [Exc. 9.10].
• Seventh week: All polynomial stretches are equivalent cntd. Unpredictability implies pseudo-randomness (without proof) [Thm 9.11]. Goldreich-Levin theorem [Thm. 9.12]. Pseudorandom function generators [Sct. 9.5.1]. Goldreich-Goldwasser-Micali construction [Thm 9.17]. Natural proofs [Ch. 23].
• Eighth week: Natural Proofs cntd. Decision trees [Ch. 12]. Computational, combinatorial and analytical complexity measures of Boolean functions and their polynomial equivalence [26].
• Ninth week: Algebraic complexity [28], see also [Ch. 16]. The degree bound (without proof) [28, Sct. 6]. Baur-Strassen Lemma [28, Sct. 7]. Bilinear complexity [28, Sct. 10]. Valiant's complexity classes [Ch. 16.1.4]. Uniform algebraic models [Ch. 16.3]. Proof Complexity [29], see also [Ch. 15].
• Tenth week (short): Proof Complexity cntd. Philosophical discussion, circuit tautologies, connections to Natural Proofs, pseudorandom generators etc. [30, Introduction]. Feasible Interpolation [Ch. 15.2.2]. Cutting planes and feasible interpolation for this system [29, Sct. 7.2.1].
• Literature.
1. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
2. S. Cook, A Taxonomy of Problems with Fast Parallel Algorithms, Information and Control 64 (1985) pp 2-22.
3. I. Wegener, Complexity of Boolean Functions (aka as The Blue Book).
4. A. Razborov, Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity, Combinatorica, Vol. 10, No 1, 1990, pages 81-93.
5. M. Karchmer, R. Raz, A. Wigderson, Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity, Computational Complexity, 5(3/4): 191-204, 1995.
6. 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.
7. O. Reingold, Undirected ST-connectivity in log-space, STOC 2005, 376-385.
8. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
9. N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM, 40(3), 1993, pages 607-620.
10. N. Segerlind, S. R. Buss, R. Impagliazzo, A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution, SIAM J. Comput., 33(5): 1171-1200 (2004).
11. A. Razborov, Bounded Arithmetic and Lower Bounds in Boolean Complexity, in the volume Feasible Mathematics II, 1995, pages 344-386.
12. P. Beame, A switching lemma primer.
13. A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
14. E. Viola, Correlation bounds for polynomials over {0,1}, ACM SIGACT News, 40(1), 2009.
15. D. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, 38:1 (1989), 150-164.
16. D. Barrington, H. Straubing, D. Therien, Non-uniform automata over groups, Information and Computation, Volume 89, Issue 2, December 1990, Pages 109-132.
17. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
18. M. Karchmer, A. Wigderson, Monotone Circuits for Connectivity Require Super-Logarithmic Depth, SIAM J. Discrete Math, 3(2): 255-265 (1990).
19. R. Raz, A. Wigderson, Monotone Circuits for Matching Require Linear Depth, J. of the ACM, 39(3): 736-744 (1992).
20. W. Gowers, Quasirandomness Counting and Regularity for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing , Volume 15 , Issue 1-2 , Jan 2006 , pp 143-184.
21. A. Razborov, On Small Depth Threshold Circuits, in Proceedings of the SWAT 92, Lecture Notes in Computer Science, vol. 621, 1992, 42-52
22. A. Yao, On ACC and threshold circuits, Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 619-627, vol.2, 1990.
23. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4): 612-625, 2002.
24. A. Razborov, Communication Complexity.
25. J. Hastad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64.
26. H. Buhrman and R. de Wolf, Complexity Measures and Decision Tree Complexity: A Survey, Theoretical Computer Science, 288(1):21-43, 2002.
27. Y. Shi, Approximate polynomial degree of Boolean functions and its applications, Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
28. V. Strassen, Algebraic Complexity Theory, Chapter 11 of Handbooks of Theoretical Computer Science, Volume A (Algorithms and Complexity), 1990.
29. A. Razborov, Lecture notes on Propositional Proof Complexity.
30. A. Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution.