\( \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.


In order they were written ...

  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.16 (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)




Return to the home page of the book