\(
\def\<#1>{\left<#1\right>}
\newcommand{\CC}{\mathbf{C}}
\newcommand{\disjpairs}{\mathcal{D}}
\DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}}
\)
Here I am going to collect comments, suggestions, pointers to results and other
stuff related to the contents of the book. Newly added/modified comments, or newly added
links to new developments are marked by .
I am using MathJax to type math.
If math symbols are not processing, try a hard refresh,
which is executed by holding your Shift key
and then clicking the Refresh/Reload/whatever button in your favorite browser.
Comments
In order they were written ...
 An $\Omega(n^3)$ lower bound for matrix product
over the semiring (min,+) [ PDF] (April 2012)

Smalldepth DeMorgan formulas from $AC^0$ formulas [ HTML]
(November 2012)
 Research Problem 1.33 is now solved! [HTML]
(January 2013).
 Research Problem 19.12 (in the bipartite case) is also now solved!
[Inf. Process. Letters]
[manuscript]
 A stronger version
of Lemma 19.11 for cuttingplanes, observed by
Daniel Apon [ArXiv]
(January 2013)
 Size of universal switching networks and formulas [HTML]
(March 2013)
 Highly differentiable boolean functions require superlinear DeMorgan formulas
[HTML]
(March 2013)
 On XOR versus OR circuits
[HTML]
(April 2013)
 The first lower bound for monotone depth3 $AC^0$ circuits [HTML]
(April 2013)
 A general lower bound for formula size of symmetric boolean functions [HTML]
(April 2013)
 What have readonce branching programs to do with $NL/\mathrm{poly}$?
[HTML]
(April 2013)
 On the UniqueDisjointness matrix [HTML]
(July 2014)
 New progress on RankConjecture [HTML]
(July 2014)
 On the "circuit hierarchy" theorem [HTML]
(August 2014)
 Two notes on Thm. 9.17
(monotone switching lemma) [HTML]
 How many linear inequalities do we need to represent monotone boolean functions? [HTML]
(December 2014)
 Simpler proof of Theorem 14.2 [HTML]
(January 2015)
 Research Problem 16.12
is now almost solved!
[HTML]
(November 2015)
 Bipartite formula complexity: a progress towards Problem 6.57 [HTML]
(February 2017)
 On Shannon function for $AC^0$ circuits
[HTML]
(July 2017)
 More on Tardos' function
[HTML]
(August 2017)
 Notes on Theorem 9.26 (monotone circuits for graph properties)
[HTML]
(January 2018)
 Notes on Lemma 3.6 (making coverings disjoint)
[HTML]
(April 2020)
 Research Problem 14.16 (sensitivity conjecture) is solved!
[HTML]
(September 2020).
Actualization [HTML] (March 2024)
 Tilling matrices and their complements [HTML]
(February 2021)
 Notes on monotone arithmetic circuits [HTML]
(February 2021)
 Research Problem 8.7 (monotone circuits vs. monotone span programms) solved!
[HTML]
(December 2021)
 Monotone simulations of negations [HTML]
(January 2023)
 Explicit dense $K_{2,2}$free graphs with small CNF representation HTML]
(January 2024)
Papers
 Lozhkin's survey (with proofs) "Refined bounds on Shannon's function for complexity
of circuits of functional elements " [PDF]
 An "unknown" note by Khrapchenko "A quadratic complexity lower bound based on the continuity of the second derivative"
[PDF]; translated by
Igor Sergeev. Original paper in Russian [PDF]
 Lupanov's paper
"On rectifier and switchingandrectifier circuits" (1956) [PDF],
translated by Igor Sergeev
 Those who can read Russian can find some old
papers of Russian mathematicians on circuit complexity
here
 In this
paper (in Russian),
Cherukhin proved that almost all symmetric boolean functions require
formulas of size
$\Omega(n\log n)$ over any finite basis. This improved the previous
lower bound of $\Omega(n\log\log n)$ due to Pudlak, Theorem 6.20 in the
book. (Thanks to Igor Sergeev for pointing to this.)
Books

O.B. Lupanov, Asymptotic Bounds on the Complexity of
Control Systems, 1984 [DJVU file, in Russian].
 Ingo Wegener,
The Complexity of Boolean Functions , 1987 [PDF]

John E. Savage, Models of Computation:
Exploring the Power of Computing, 1998
[Available from Book's homepage]
Notes:
 Results of Nechiporuk, mentioned in Sect. 13.6.2, can be also found in:
Nechiporuk E. I. Rectifier networks, Soviet Physics Doklady, 1963. Vol. 8. 57.
Local copy
Return to
the
home page of the book