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].