Student logic seminar (Fall 2020)

A talk assignment and literature

Topics

  • (1) [14.X.2020, L.Kundratova and her slides]
    Circuits, their depth and size, the theorem that p-time algorithms give rise to a family of p-size circuits, Shannon's or Muller's thm.

    Boppana-Sipser [BP], pp.6-9, also Sipser [S], Sec.9.3 up to Thm.9.30 (pp.351-358), or [K1] Sec.3.1.

  • (2) [21.X.2020, M.Grego and his slides]
    Formulas, their depth and size. Spira's lemma. Formula depth and communication complexity. Khrapchenko's thm.

    [K1] Sec.3.1 or [K2] Sec1.1. for formulas,
    Wegener [W] p.219 or [K2], L.1.1.4 for Spira's lemma,
    Karchmer-Wigderson [KW], Sec.2 or [K2] Sec.17.4 (Thm.17.4.1) for the relation depth <--> comm.complexity.

  • (3) [4.XI.2020, R.Reza and her slides.]
    Characterization of circuit size in terms of PLS problems and communication complexity.

    Razborov [R], Sec.3, or Thm.17.4.3 in [K2].
    Few pictures motivating the topic.

  • (4) [11.XI.2020, L.Folwarczny and his slides]
    Lower bound for monotone circuits

    [BP] Boppana-Sipser, Secs.4.1.-4.3, or papers by Alon-Boppana or by Berg-Ulfberg.

  • (5) [18. and 25.XI., and 2.XII.2020, M.Narusevych and his slides and a correction to one page]
    Topology and some problems in complexity theory

    Sipser [S84] and possibly Freedman [F].

  • (6) [9.XII.2020, O.Jezil and his slides]
    The fusion method (aka ultraproduct)

    Wigderson [Wi] Secs.1+2 + (if time permits) 3, or pp.10-12 in [K1].

  • (7) [16.XII.2020, J.Krajicek and his slides]
    Rounding up the seminar: pluses and minuses of circuit complexity approach to P vs. NP


    Literature

    The online material is not meant for a distribution but only for study purposes - thanks.

  • [B] P.Beame, his 3-page notes on the Karp-Lipton thm and Kannan's thm, 2016,

  • [BP] R.Boppana and M.Sipser, The complexity of finite functions, online.

  • [F] M.Freedman, Topological views of computational complexity, online.

  • [KW] M.Karchmer and A.Wigderson, online .

  • [K1] J.K., Bounded Arithmetic, Propositional Logic and Complexity Theory, CUP, 1995.
    See my page and I will make a copy available to participants of the seminar.

  • [K2] J.K., Proof Complexity, CUP, 2019.
    Same link as in [K1] - a version of the book (final draft) is online there.

  • [R] A.A.Razborov, Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Izvestiya RAN., 59(1) (1995), 201-224. Online.

  • [RR] A.A.Razborov, S.Rudich, Natural proofs, in: Proc. of the 26th Annual ACM Symposium on the Theory of Computing, (1994), 204-213. online.

  • [S84] M.Sipser, A topological view of some problems in complexity theory, online.

  • [S] M.Sipser, Introduction to the Theory of Computation, online (36Mb!).

  • [W] I.Wegener, The Complexity of Boolean Functions, available online

  • [Wi] A.Wigderson, The fusion methods for lower bounds in circuit complexity, online.