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

1. An $\Omega(n^3)$ lower bound for matrix product over the semiring (min,+) [ PDF] (April 2012)
2. Small-depth DeMorgan formulas from $AC^0$ formulas [ HTML] (November 2012)
3. Research Problem 1.33 is now solved! [HTML] (January 2013).
   
4. Research Problem 19.12 (in the bipartite case) is also now solved! [Inf. Process. Letters]    [manuscript]
5. A stronger version of Lemma 19.11 for cutting-planes, observed by Daniel Apon [ArXiv] (January 2013)
6. Size of universal switching networks and formulas [HTML] (March 2013)
7. Highly differentiable boolean functions require super-linear DeMorgan formulas [HTML] (March 2013)
8. On XOR versus OR circuits [HTML] (April 2013)
9. The first lower bound for monotone depth-3 $AC^0$ circuits [HTML] (April 2013)
10. A general lower bound for formula size of symmetric boolean functions [HTML] (April 2013)
11. What have read-once branching programs to do with $NL/\mathrm{poly}$? [HTML] (April 2013)
12. On the Unique-Disjointness matrix [HTML] (July 2014)
13. New progress on Rank-Conjecture [HTML] (July 2014)
14. On the "circuit hierarchy" theorem [HTML] (August 2014)
15. Two notes on Thm. 9.17 (monotone switching lemma) [HTML]
16. How many linear inequalities do we need to represent monotone boolean functions? [HTML] (December 2014)
17. Simpler proof of Theorem 14.2 [HTML] (January 2015)
18. Research Problem 16.12 is now almost solved! [HTML] (November 2015)
19. Bipartite formula complexity: a progress towards Problem 6.57 [HTML] (February 2017)
20. On Shannon function for $AC^0$ circuits [HTML] (July 2017)
21. More on Tardos' function [HTML] (August 2017)
22. Notes on Theorem 9.26 (monotone circuits for graph properties) [HTML] (January 2018)
23. Notes on Lemma 3.6 (making coverings disjoint) [HTML] (April 2020)
24. Research Problem 14.5 (sensitivity conjecture) is solved! [HTML] (September 2020).
    Actualization [HTML] (March 2024)
25. Tilling matrices and their complements [HTML] (February 2021)
26. Notes on monotone arithmetic circuits [HTML] (February 2021)
27. Research Problem 8.7 (monotone circuits vs. monotone span programms) solved! [HTML] (December 2021)
28. Monotone simulations of negations [HTML] (January 2023)
29. Explicit dense $K_{2,2}$-free graphs with small CNF representation [HTML] (January 2024)
30. Lower bounds for monotone real circuits via finite limits [HTML] (Juli 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 switching-and-rectifier 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. 5-7. Local copy