About Arora and Barak’s Book

Errata

I checked the authors’ website and the publisher’s website but did not find errata. So, I wrote some below.

• P. 72, 2nd bullet, “Thus for large enough formulae \(\psi\) … string of the type \(\psi 01^{H(\card{\psi})}\) ….” It should be \(\psi 01^{n^{H(\card{\psi})}}\).

• P. 75, 1st paragraphy, “… ensuring \(1^n \in B_u\).” It should be \(U_B\).

• P. 114, last (line) equation in the Meyer’s Theorem, “\(T(x, C(i), ...)\),” I suppose that \(T\) should also take \(i\) as input, where \(i\) is polynomial in the input size \(n\) as the computation time is exponential in \(n\).

• P. 131, Definition 7.6, \(x\notin L\) should imply that \(\Pr[M(x)=0] = 1\).