Errata for Computational Complexity: A Modern Approach

Errata for Computational Complexity: A Modern Approach (by Sanjeev Arora and Boaz Barak).

Mostly from Parts 2 and 3 of the book. If you find something I haven't, email me at: first-name . last-name @ gmail.com - Daniel Mitropolsky

Chapter 18 (Average case complexity: Levin's theory)

• pg. 368, the statement and proof of Lemma 18.9 are wrong. First, it is not possible that \(|g(x)| = |x|+2\) and that it have property (3). For instance the probability of some \(x\) is 1 then \(\mathbb{P}[g(x)=g(D_m)] \leq 2^{-|g(x)|+1}\) is clearly false. There are many other mistakes; the Lemma, and Proof of Theeoreme 18.8, can be fixed as follows:
• Remove condition 2.
• Condition 3 should be restated as: for any \(y \in g(\{0,1\}^n)\), \(\mathbb{P}[y=g(D_n)] \leq 2^{-|y|+1}\)
• In the first part of the proof, it is not true that the \(h\) given is 1-1. First, it is not injective on \(x\) with probability 0 (if \(x\) has prob. 0, then \(h(x) = h(x-1)\)). Furthermore, it is not injective on inputs of different length; there are many scenarios (even for non-zero probability inputs) where \(h(x) = h(x')\) for \(|x|\neq|x'|\). However, it is true that for any \(n\), \(h\) is injective on \(\{x \in \{0,1\}^n~:~\mathbb{P}_{D_n}(x)\neq 0 \} \).
• Similar to above, \(g\) is injective only on same-length inputs (i.e. on \(\{0,1\}^n\) for any \(n\)).
• Remove the part about padding \(g\), indeed it is critical that \(g(x)\) be much shorter than \(x\) in some cases (when \(x\) has high prob. under \(D\)). Then the revised version of condition 3 is met.
• It is still an issue that \(g\) is not injective on \(\{0,1\}^*\) since the proof of Theorem 18.8 relies on this critically (otherwise, the reduction in that proof does not satisfy Correctness). There may be a few ways to fix this, but one is to modify the definition of \(g(x)\) or those \(x\) s.t. \(\mathbb{P}_{D_n}[x] > 2^{-n}\) to be \(|x| || h(x)\) (ignoring some trivial details about extra bits to represent separators, etc). Including the length of \(x\) clearly makes \(g\) injective on all of \(\{0,1\}^*\). Most importantly condition 3 can be modified to say for any \(y \in g(\{0,1\}^n)\), \(\mathbb{P}[y=g(D_n)] \leq n2^{-|y|}\). The proof of Theorem 18.8 still goes through even with this bound, because the probability of a tuple given by the reduction, \(\langle M',y,1^t \rangle \) of length \(m\), has probability at most \(n2^{-|y|}\). Since by construction (in proof of 18.8) we have \(m > t > n\), the probability is upper bounded by \( m2^{-|y|} \leq m^3 (2^{-\log m}2^{-|y|}\frac{1}{m}) \) (i.e. Domination holds).

Chapter 19 (Hardness amplication and error-correcting codes)

• pg. 376, in statement of Lemma 19.3 it should say for every \(x\in\{0,1\}^n\) not \(x\in\{0,1\}^*\)
• pg. 378 in second-to-last paragraph of proof, it should say define \(C(x)\) to equal the majority of \(C_1(x),\ldots,C_t(x)\).
• pg. 383, top line of page should say the distance might decrease from \(\delta\) to \(\delta/2\).
• pg. 383, Lemma 19.11: The Reed-Solomon code has distance \(1-\frac{n-1}{m}\). (Indeed for \(n=m\) the current statement gives a trivial distance of \(0\), but the code is invertible). Relatedly, in the proof it should say nonzero \(n-1\) degree polynomial has at most \(n-1\) roots (not \(n\)).
• pg. 383, last paragraph. The remark about obtaining the Walsh-Hadamard code as a special case of Reed-Muller codes is not true as stated. Setting \(d=1\) and \(\mathbb{F}=\mathbb{F}_2\) results in a code \(\mathbb{F}_2^{l+1}\rightarrow \mathbb{F}_2^{2^l}\); interpreting the domain as \(\{0,1\}^n\) (i.e. \(n=l+1\)) this gives a code mapping \(x \in \{0,1\}^n\) to a \(2^{n-1}\) long string \(z\) where for \(y\in\{0,1\}^{n-1}\) we have \(z_y = x_0 + x_{[1:n]}\odot y \mod{2}\). However, the suggested code can be obtained too by considering the function \(f_x(a) = P(a,x_1,\ldots,x_n)\) as a code of \(x\).
• pg. 38, in Proof of Theorem 19.15, remove second sentence of "Randomized interpolation" (Assume that \(t\) is quite large...)
• pg. 385, in Proof of Theorem 19.15, Randomized interpolation, should say \((d+1)\frac{m-1}{m} \leq \frac{1}{2}\).
• pg. 399, Exercise 1 not true as written, should say ask to prove \( \mathbb{P}[X=1] = 1/2 + (-1)^{k+1}(1-2\delta)^k/2 \).

Chapter 21 (Pseudorandom constructions: Expanders and extractors)

• pg. 430, in the proof of Claim 2 the 2nd inequality is missing a factor of \(d\) in the RHS sum, it should say \( \frac{2}{d}\sum_{k=1}^{n/2}d\rho k(\mathbf{v}_k^2 - \mathbf{v}_{k+1}^2) \)
• pg. 430, in the proof of Claim 2 the last line has a typo, it should say \(\frac{2}{d}d\rho \sum_{k=1}^{n/2}k\mathbf{v}_k^2 - (k-1)\mathbf{v}_k^2 = 2\rho\sum_{k=1}^{n}\mathbf{v}_k^2 = \cdots \)
• pg. 434, in the statement of Theorem 21.15 it should say \(|B| = \beta n\) not \(\beta N\)
• pg. 439, at the end of the proof of Claim, the run time is incorrectly given as \(n^{\log 100}\) (\(n\) is not even defined in this Claim). It should be \(100^{\log k}\) which is indeed \(\mathbf{poly}(k)\) as needed
• pg. 441, second paragraph of 21.4.1 should say that \(G_k = (G_{k-1}\circledR H)^{50}\) is a \(d^{50}N\)-vertex graph with degree \(d^{50}\), not \(d\) (though anyway both are constants).
• pg. 441, in the statement of Claim it should say \(G_k\) is a \(d^{50k}n,d^{50},1-\epsilon\) expander, not \(d^{20}\) (though anyway both are constants).
• pg. 445, in Lemma 21.26 it should say \(\Delta(H(X)\circ H, U_m\circ H) < \epsilon\), i.e. \(U_m\) not \(U_n\)
• pg. 448 (TODO) Need to confirm, but Theorem 21.28 is not just a constructive version of 20.7, since I think that proof only gives \(R^{D}(a,x)\) that would be correct on most \(x\), not all.
• pg. 451, in Definition 21.33 the piecewise definition of \(G_k(a\circ z)\) should say \(k=0\) on top and \(k \geq 1\) on the bottom.
• pg. 452, in the proof of Lemma 21.34, the trivial base case is \(k=0\) and not \(k=1\) (credit: Tom Knowles, Apr 2021).