If you noticed some other errors/misprints/unclear parts, please let me know.
- p.30, the last sentence of the proof of L.3.4.2: This proves the statement for non-standard i only but for standard ones it is the hypothesis of the lemma.
- pp.76 and 96 (1st paragraphs of Sections 12.1 and 16.1): We are using L 3.3.3 even though it applied to first order structures only. Recall from the beginning of Chpt.5 that "second order" is just a misnomer and we treat K(F,G) as first order. On p.45 center it is pointed out that results proved earlier for K(F) hold equally for K(F,G).
- p.98. A hint for a proof for Theorem 16.1.4: The simplest proof is that in V^0 you can from \forall x Closure(x) prove that for any fixed m \geq 2 standard (e.g.) there are counting mod m functions for all sets. This then gives via simple witnessing a low degree polynomial over F_2 defining counting mod 3 with a small error - that is a contradiction.
- p.117: The notation (T,\ell) is used on line -9 without explaining what \ell is. This follows the notation from 7.1 where labelled trees appeared first.
- p.170, line -3: the bound 2^{n^n} is just a very generous bound (I prefer simple terms).
- p.198, L.30.1.1, proof sketch:
If NE \cap coNE have size s circuits then the tau-formula from Possibility A is not a tautology for any L in NE \cap coNE (i.e. the formula determined by the characteristic string of L restricted to strings of size k) and hence - by Poss.A - the truth-table function with parameter s is hard for every pps P (so NP \neq coNP).
- L.31.2.1: There is a gap in Claim 3 in the proof (the argument does not take into account those inputs u to C which determine sample a(u,e) which is in U but not in W) and, in fact, the lemma does not hold as stated (e.g. the region of undefinability of an \alpha querying just one line i and then aborting or stopping with 0 respectively will be almost a half of the sample space).
To resurrect the lemma one needs to alter the construction just a little bit: take for the sample space not the whole of \Omega_b (p.208) but just its suitable subset \Omega^*_b (still infinite and an element of the ambient model to conform with Sect.1.2) for which the lemma holds - a sort of "hard-core" of the sample space. There is a simple model-theoretic argument that such suitable set exists in which the original L.31.2.1 (more precisely, what the lemma actually proves) is used.
Remarks:
(1) The existence of a nonstandard model of T_{PV} in which \exists x NW_{A,f}(x)=b holds and the resulting consistency of Razborov's conjecture and even of the stronger statement (S) (i.e. the context of Sects.31.3 and 31.4) has been also established "classically" (via the KPT witnessing and a version of L.31.2.1 in which the Student /Teacher solve (T) for all inputs, i.e. W is everything, and the problem mentioned above is avoided) in my subsequent paper.
(2) For the program of reducing lower bounds for strong proof systems to circuit hardness assumptions, an acceptable form of the assumption is that every circuit performing some specific task needs to be large (see Chpt.27 and p.175 bottom).
In particular, form my point of view it would be OK to use an assumption that every circuit computing a strategy of the Student solving task (T) (or some similar task) over a particular sample space with a positive probability needs to be large. The further reduction to the hardness of the function f is "an extra": it is nice if one's assumption follows from a standard one but it is not really that important.
I am indebted to S.Buss (San Diego) for pointing out most of these errors.
Acknowledgements