- 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 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 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 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 165, line 14: "$\{0,1\}^k$" $\to$ "$\{0,1\}^r$" (Sasha Golovnev)
- 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 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 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 263, line -1: "Pudlak et al. (1997)" $\to$ "Pudlak (1997)"
- page 264, 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 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
- pahe 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 344, line -1: "$n/32$" $\to$ "$n/16$" (Yuping Shen)
- 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 the
**re**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 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 434, Thm. 14.40: "iterated majority" $\to$ "iterated NAND function" (Igor Shinkar)
- page 440, Thm.15.1: Factor $1/4$ can be replaced by $1/2$
- page 475, Lemma 16.26: Its proof is not quite correct (Navid Talebanfard)

See here for my correction. - page 455, Ex. 15.2(b): Here, the underlying graph of the constructed NBP is not required to be acyclic (Meena Mahajan)
- page508, line 5: replace $C_j(\alpha)=1$ by $(\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 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)

Return to
the home page of the book