Forcing with random variables and proof complexity

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.

- p.44,l.-2: Lower case \theta ought to be upper case \Theta.

- 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.80: the definition of \Delta is found after L.12.1.2 and not in Thm.12.2.1.

- 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.107: Two lines before 18.1.1 I sloppily state that there is a function symbol for s(k) in L_n. However, the cut {\cal M}_n is not necessarily closed under a subexponential s(k) (e.g. 2^{k^{1/t}}) and hence there is no symbol for the function in L_n. But it is not needed later on: one only needs that s(n) is in the cut (which it is). To have the formula Prf_P bounded add a new free variable y to bound Y and in the particular case substitute s(n) for y. (We wouldn't need y if we had in L_2 the symbol |Y| for max(Y)+1 used by Cook and Nguyen in their book).

- 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.

- pp.154-155: This section is messed up: the notation and the definition of RSA are incorrect and this makes the presentation of Thm.24.1.1 hard to follow. RSA send x to x^e mod N, of course. The sample space should consists of RSA pairs (e,N) (where e,N satisfy the conditions for g,N on p.154) and cipher texts. The construction shadows then the proof of Thm.3 and Cor.4 in [76]. More details are in J.Maly's MSc. Thesis (Chpt.3) at the Universitat Wien, 2016.

- 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 (or see a proper paper) 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 Sam Buss (San Diego) for pointing out some of these errors. He had also some other comments on the book in his BLS review.

Acknowledgements

I thank Yuval Filmus (Toronto), Erfan Khaniki (Tehran) and Jan Maly (Vienna) for pointing out some errors and typos.