S. Jukna and I. Sergeev, "Complexity of Linear Boolean Operators" -- List of errata

• page 8, line 5: Rectangles need not be square matrices
• page 13, Lindsey's Lemma:should be $ab\leq n$
• page 19, line 11: Should be $\sim kn$
• page 22, Lemma 2.5: Should be $+ n$ for the case when $r<\log n$
• page 36, Theorem 3.12: The bound on OR$_d(A)$ here holds only for layered OR-circuits of depth exactly (not at most) $d$ (thanks to Timur Khanipov).
  The circuit being layered is only used in the proof of the 2nd claim of Lemma 3.14 (to carry out the induction on the tree-depth).
  Theorem 3.3 is also proved under the same (being layered) restriction.
• page 42, line 10: Missing reference [98] for Selezneva
• page 75, Lemma 5.6: Wrong reference, should be:
  • P. Pudlak and V. R"odl (2004): Pseudorandom sets and explicit constructions of Ramsey graphs, in: Quaderni di Matematica, Vol. 13, Dipartimanto di Matematica, Seconda Universita di Napoli, Caserta - 2004, editor J. Krajicek, pp.327-346
• page 76, Thm. 5.8: Replace $A$ by $H_S$
• page 78, line -4: Remove minus $-$ from the definition of $\Delta$
• page 79, line 10: "of an $\times n$ matrix" should be "of an $n\times n$ matrix" (Dmitri Maslov)
• page 90, line -5: Replace "later" by "latter"
• page 94, line 7: Replace $(2,m-k+1)$ by $(m-k+1,2)$
• page 113, line -8: Replace "$n\times n$ requiring" by "$n\times n$ matrices requiring"
• reference [30]: Replace the first occurrence of "Korhonen" by "Matti Järvisalo"
• reference [32]: The range is 234-236
• reference [41]: Volume is 44, not 4
• reference [106]: Replace "methods" by "arguments"