Errata for the first draft (of January 2006)
===============================================

The definition of monotone functions on page 41 is of course wrong.
The definition should be as in Appendix B.2.2. 
[Thanks to Or Meir. May 29, 2006]  

Typo in Construction 6.23 (Sec 6.2.2.1). 
In Item 2, the approximation obtained is $p_i \pm \epsilon'$.
[March 31, 2006]
 
Re UNIQUE SOLUTION PROBLEMS (Sec 6.2.3).
Errata to the proof of Thm 6.27 -- inequality (6.10).
This inequality (as stated) is incorrect. 
But the relevant probability can be lowerbouded
as necessary, when considering $m=(log_2|R(x)|)+1$
rather than $m=log_2|R(x)|$. The probability we are
interested in equals the probability of some element
passing the sieve minus the probability of at least two
elements passing it, which can be lowerbounded via
Inclusion/Exclusion by $|R(x)|\cdot2^{-m}-|R(x)|^2\cdot2^{-2m}$
(note that the second term is twice bigger than as appearing in the text).
[March 21, 2006]

Re UNIFORM GENERATION OF SOLUTIONS (Sec 6.2.4).
The reduction of approximate counting to uniform
generation (Part 2 of Thm 6.29) seems to require a stronger
notion of parsimonious reduction allowing efficient 1-1 mapping
of $R'(g(x;y'))$ to $R(x;y')$. This stronger condition is also
satisfied by many natural search problems (e.g., SAT).
[March 23, 2006]

Re EXERCISE 6.13 (a hierarchy theorem for promise BPtime).
The guideline is inadequate yielding diagonalization only
against machines that can satisfy the BP-condition on 
each input, whereas we need to daigonalize against any 
machine that satisfies the BP-condition on inputs in the promise. 
The claim can be established by using "delayed diagonalization"
(as in the proof of Thm 4.6). 
[Thanks to Dieter van Melkebeek. January 15, 2007] 

Re the formulation of Thm 7.8. The formulation contains a typo.
The text "for every $x\in\{0,1\}^n$ given oracle access to any $B_x$" 
(in 3rd line) should be omitted. 
[Thanks to Or Meir. May 29, 2006]  

Typo in THM 8.18 and in Exer 8.17: 
It should be $S:\N\times\N\to2^\N$ (not $S:\N\times\N\to\N$).
[Thanks to Or Meir. May 29, 2006]  

Re proof of Thm 9.4 (Sec 9.1.2.2).
A slightly different arithmetization is used in the extension to #P.
Similarly, the extension to PSPACE (as presented) actually yields
a proof system for the complement of QBF.
[April 25, 2006]

Re Sec 9.3.2.1, the analysis of the Testing of the Hadamard Code.
Exercise 9.16 only implies that if the table is 0.02-far from
linear then it is rejected with probability 0.01 (rather than
if it is 0.02-far from linear then it is rejected with probability 0.02). 
Thus, in the rest of the proof we should assume that each table 
is 0.02-close to being linear. [June 12, 2006]

The specific expression given for Chernoff Bound (in Apdx D.1.2) 
may be wrong. The exponent should be either $-(\delta^2/(4p(1-p)))\cdot n$
(i.e., a factor of two smaller than stated) or $-2\delta^2\cdot n$. 
(Both alternatives are correct, but one usually sees the latter.) 
[Thanks to Kivanc Mihcak, February 2007]