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.