Boolean Function Complexity: Advances and Frontiers

List of errata

• page 7, line -15: "smalest subset" should read "subset".
• page 10, line -4: "$1\leq k\leq m$" $\to$ "$1\leq k\leq n$" (Igor Sergeev)
• page 16, Fig. 1.4: duplicated "$\lor$"
• page 16, Example 1.7 and before: The measure $C(f)$ of circuit complexity is defined only later on page 22 (Andras Salamon)
• page 20, 8th line below Fig. 1.9: "$2n-3$" should read "$2n-2$" (Liang Hong)
• page 21, 1st line of Def, 1.11: delete "their" (Liang Hong)
• page 24, line -9 and page 25, line -15: replace $2^n/m$ by $2^{n-k}/m$ (Pierre McKenzie)
• page 25 line -11: $\leq \frac{2^n}{m} + 2^k$ should read $= \frac{2^n}{m}$ (Pierre McKenzie)
• page 25, line -10: "computed by $F_3$" should read "computed by $F_4$" (Pierre McKenzie)
• page 30, Lemma 1.2: Replace $(9t)^t$ by $(15t)^t$. The mistake is in the the 3rd inequality on line -3: it should be $\leq 3^t(r/t + 1 - 1/t)^t\leq 3^t(4t+1)^t\leq (15 t)^t$ (Silas Rathke)
• page 31, proof of Theorem 1.22: replace $(9t)^t$ by $(15t)^t$, and $(18nt)^t$ by $(30nt)^t$ (see the previous correction)
• page 40, Fig. 1.12: wrong order of figures; "a" corresponds to Case (b) (Andreas Krebs)
• page 53, Table 1.4: reference "Boppana (1986)" should be "Boppana (1985)" (Igor Sergeev)
• page 57, Lemma 2.1: The condition "if $f$ is a boolean function of $n$ variables" is missing in the statement of the lemma (Liang Hong)
• page 62, line -12: "true=0" $\to$ "true=1" (Igor Sergeev)
• page 68, line -11: "Error(f,..." $\to$ "Error(p,..." (Sasha Golovnev)
• page 73, line -9: "$g(x)^2$" $\to$ "$q(x)^2$" (Nitin Saurabh)
• page 85, Lemma 3.5: $2/3$ $\to$ $3/2$ (Sasha Golovnev)
• page 86, Lemma 3.6 : The proof is not complete (Hans U. Simon)
  See here for a corrected proof.
• page 95, line -9: "primitive $0$-$1$ matrices $R_i$" should read "real rank-$1$ matrices $R_i$" (Lianna Hambardzumyan)
• page 112, line 4, Thm. 4.25: In the definition of the matrix $B$ one should take "or" instead of "and", as in original paper of Nisan and Wigderson. (Hans U. Simon)
  See here for a correction.
• page 161, line -11: "If $H(1,x)=0$ then $H(0,y)=0$" $\to$ "If $H(1,x)=0$ then $H(0,x)=0$" (Hamidreza Jahanjou)
• page 162: There is an extra right parenthesis in (6.8): $L(H^{\land}))$ should be $L(H^{\land})$ (Liang Hong)
• page 165, line 14: "$\{0,1\}^k$" $\to$ "$\{0,1\}^r$" (Sasha Golovnev)
• page 170, Theorem 6.13: In fact, Hastad proved $\Gamma=2-o(1)$, the $o(1)$ factor was eliminated by Avishay Tal [FOCS, 2014] (Igor Sergeev)
• page 175, line -8: ``contains a parity function of $d$ variables or its negation'' should read ``contains an affine function of $d$ variables'', because an affine function on $x_1,\ldots,x_m$ has the form $a_0\oplus a_1x_1\oplus\cdots\oplus a_mx_m$ for some $a_i\in\{0,1\}$. (Sasha Golovnev and Sasha Kulikov)
• page 179, line -1 and page 180, line 2: replace $a_ib_i$ by $s_it_i$ (Igor Sergeev)
• page 207, line 6: "Jukna (2008)" $\to$ "Jukna (2006)"
• page 207, Claim 7.3: $\mathrm{rk}(M_R)=1$ should be $\mathrm{rk}(M_R)\leq 1$ (Jan Polster)
• page 207, last line: "$y=\{u,v\}$" should be "$\{u,v\}=x$
• page 208, lines 2-4: Should read "We have to show that the rows of the submatrix $M'$ of $M$ corresponding to the edges in $F$ cannot sum to the all-$0$ vector over GF$(2)$" (Jan Polster)
• page 213, line 14: the first chapter $\to$ the third chapter
• page 214, line -14: "$c(u)=c(v)$" should be "$c(u)\leq c(v)$", to ensure that $c(u)=0$ and $c(v)=1$ holds for a found edge $e=(u,v)$ (Jan Polster)
• page 217, Lemma 7.19: the given proof holds also for any $\alpha\geq 12/m$, not necessary $\alpha\geq 16/m$ (Jan Polster)
• page 224, proof of Theorem 7.26, line 6: should be "$c_q$", not "$c_p$" (Igor Sergeev)
• page 226, after Corollary 7.27: Borodin et al. (1982) consider only bipartite perfect matching problem $BPM$; but, as shown in Raz-Wigderson's paper, the game $FE_m$ can be reduced to the game for $BPM$ (Vladimir Podolskii )
• page 246, line -4: "core $T$" $\to$ "core $E$" (Igor Sergeev) page 248, lines 17-20: replace $\lfloor X_i\rfloor \land \lfloor Y_i\rfloor$ by $\lfloor X_i\rfloor \land \lfloor Y_j\rfloor$ (that is, $Y_i$ by $Y_j$) (Igor Sergeev)
• page 259, Thm. 9.17: Here is what to do when one of the approximators $\CC{f}$ or $\DD{f}$ becomes empty along the way.
• page 262, proof of Thm. 9.19: The argument used in Case 2 of the proof is buggy (Ho Boon Suan, Austen Fan)
  Here is a corected argument.
• page 263, line -1: "Pudlak et al. (1997)" $\to$ "Pudlak (1997)"
• page 268: The proof given here is too short and not correct (Anastasia Sofronova)
  See here for a correct proof.
• page 272, Thm. 9.28: Should read "There are clique-like graph functions $\varphi$ such that ..."
• page 273, lines 3-5: the question is stated in a wrong direction; the question is whether every monotone real circuit can be efficiently simulated by a non-monotone boolean circuit
• page 278, line -1: replace one of "${\cal A}_1$" by "${\cal A}_2$"
• page 283, line 9: remove "in the lemma"
• page 296, Remark 10.20: The improvement of Beals et al. (1998) allows to replace factor $\log^2n$ by factor $\log n$ also in Theorem 10.1. This was shown earlier in Chapt. 4 of "R. Beals, Improved construction of negation-limited circuits, DIMACS Tech. Rep. 95-31, 1995" (Igor Sergeev)
• page 303, line -14: "OR of DNFs" $\to$ "OR of CNFs" (Yuping Shen)
• page 304, line 1: The Shannon function for $AC^0$ circuits behaves as $2^{n/2}$, and as $2^n/n$ for the size (not leafsize) of $AC^0$ formulas see here for details.
• page 307, line -14: "neg-fanin and" $\to$ "neg-fanin $k$ and" (Yuping Shen)
• page 308, line -5: "$+/3$" $\to$ "$+1/3$" (Yuping Shen)
• page 309, line 9 in the proof of Lemma 11.7: "each vector in $B$'' should be "each vector in $B'$" (Igor Sergeev)
• page 311, Thm. 11.10 and the first line after it: replace $S$ by $f$
• page 323, Remark 11.28: The remark is misleading; see here for a correction
• page 330, line 12: should be "$f$ coincides with $g$ or with $\neg g$" (Igor Sergeev)
• page 330, Discriminator Lemma: replace "total weight" by "total weight $\alpha$" (i.e. insert $\alpha$)
• page 340, line -9: "is some way" $\to$ "in some way" (Yuping Shen)
• page 340, line -4: "Ajtai et al. (1983)" $\to$ "Ajtai (1983)"
• page 341, line 1: Right parenthesis should stay after "> s"
• page 341, Thm. 12.1: $(2t)^s$ $\to$ $(4t)^s$
• page 342, line 6: "$|S|\leq (2t)^s$" $\to$ "$|S|\leq (4t)^s$"
• page 342, line 11: replace "an arbitrary subset of $s'-s$ variables" by "the last $s'-s$ variables". (Since the order of clauses is fixed, the minterm $\pi'$ is actually a sequence of literals, not just a subset.) (Alexander V. Smal)
• page 343, line -10: Replace "$(2t)^s$" by "$(4t)^s$". This is because we have an additional multiplicative term $2^s$, the number of b's. Accordingly, the constant "8" in the Switching Lemma (as well as in latter its applications) should be replaced by constant "16" (Andreas Krebs)
• page 347, Case 1: "probabilitysss" should read "probability" (Igor Sergeev)
• page 348, Claim 12.9: redundant parenthesis "$((\log ...$" should read "$(\log ...$" (Igor Sergeev)
• page 349, Theorem 12.12: Formulation is somewhat misleading; see a correct formulation.
• Page 363, line -13: "if the is a function $F:\{0,1,\ldots,n\}\to\{0,1\}$" should be "if there is a function $F:\{0,1,\ldots,t\}\to\{0,1\}$".
• page 369, hint to Ex. 12.3 (b): "$b(1,k)$" $\to$ "$s(1,k)$" (Sasha Golovnev)
• page 395, line -7: By just setting to $0$ entries outside $A'$ we willl only get $(n-r/2)^2$ (Gil Cohen)
  See here how to get $(n-r)^2$.
• page 410, middle: "CREW RAM" should be "CREW ORAM" (Igor Sergeev)
• page 415, formula for $y_iS_i$: replace $y_1$ by $y_i$ (Igor Sergeev)
• page 428, line -6: The inequality $1-1/k \geq 1 - 1/\log N$ should be in the other direction, since $k$ is at most $\log N$ (Igor Shinkar)
• page 434, Thm. 14.40: "iterated majority" $\to$ "iterated NAND function" (Igor Shinkar)
• page 436, Ex. 14.9: This lower bound holds not for the function given by Eq. (14.13) but for its dual, i.e. with AND and OR interchanged (Meena Mahajan)
• page 440, Thm.15.1: Factor $1/4$ can be replaced by $1/2$
• page 455, Ex. 15.2(b): Here, the underlying graph of the constructed NBP is not required to be acyclic (Meena Mahajan)
• page 475, Lemma 16.26: Its proof is not quite correct (Navid Talebanfard)
  See here for my correction.
• page508, line 5: replace $C_j(\alpha)=1$ with $C(\alpha)=1$ (Igor Sergeev)
• page 518, Ex 18.9, line 1: "with" $\to$ "which" (Igor Sergeev)
• page 553, Ex. 19.1: "regular" $\to$ "$1$-regular", and "same degree" $\to$ "degree $1$"
• page 565, line 15: replace $T_C$ by $T_G$ (Igor Sergeev)

  page 582: line -6: $b_i=1/i-1/(i+1)$ should read $b_i=A/i-A/(i+1)$ (Liang Hong)

• page 589, 2nd inequality: should be $1-x \geq \mathrm{e}^{-x-x^2}$ for $0 < x < 0.69$ (Igor Sergeev)
• page 591: Year in "Ajtai, Komlos, Szemeredi" should be 1983 (not 1994). The full version appeared in Combinatorica 3:1 (1983), 1-19 (Igor Sergeev)
• page 599: Issue in "Hastad and Wigderson (2007)" should be 11 (not 1) (Igor Sergeev)
• page 609: In the reference "Valiant (1977)", "methods" should read "arguments" (Igor Sergeev)
• page 610: The full title of Zdobnov's paper is "On the complexity of linear function in the class of $\pi$-schemes without null chains" (Igor Sergeev)