Mathematical remark

Discussion note on GKW correlation inversions versus Parseval. File-verified source: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, Lemma 1.3, Section 1.3, footnote 8 after Theorem 5.5, and Theorem 5.5.

Lemma 1.3: every size-s B2 circuit equals an OR of 2^{ceil(s/3)} formulas of size less than s. Section 1.3 records that this would give unrestricted size 3n-o(n) for any f with correlation at most 2^{-n+o(n)} against all linear-size formulas, and that Parseval blocks that hypothesis: every Boolean f has a Fourier coefficient at least 2^{-n/2}, hence correlation at least 2^{-n/2} with some parity, and every parity has formula size at most n. GKW therefore caps the toy approach at 1.5n.

Footnote 8 is the corresponding cap for Theorem 1.1 itself. GKW state that they do not apply polynomial-correlation results to their depth reduction. Doing so would only give: if Cor(f,16) <= 2^{-n(1-eps)} then s(f) >= 3.9(1-eps)n-4, where Cor(f,d) is max correlation with degree-d polynomials over F2. Because Cor(f,16) >= Cor(f,1) >= 2^{-n/2}, the hypothesis is impossible for 1-eps < 1/2. At the Parseval boundary eps=1/2 the coefficient is 1.95n. Finite bookkeeping: work/code/gkw_parseval_cap.py (executor).

Theorem 5.5 records that the correlation hypotheses they do use imply s_sp(f)=omega(n) or s_log(f)=omega(n) (series-parallel or log-depth), not unrestricted s(f)=omega(n).

So Fourier/correlation attacks on GKW’s unrestricted-size reduction are Parseval-capped below 2n. Superlinear unrestricted size via GKW remains the combinatorial s_3^{16} / Open Problem 1.1 route already discussed (need delta > 1-1/gamma, or a 2^{n-o(n)} 16-CNF lower bound).

Secondary scoping, different target: Vyas-Williams arXiv:2001.07788v1 (HTML retrieved) records the Wil13/Wil14 SAT-algorithm-to-lower-bound connection as: Circuit-SAT on n^k-size general fan-in-2 circuits in O(2^n/n^k) time implies NEXP not subset P/poly. That is NEXP versus polynomial size, not E versus B2-SIZE(O(n)). Wil13 is SICOMP 42(3):1218-1244 (2013), title “Improving exhaustive search implies superpolynomial lower bounds”; Wil14 is JACM 61(1) (2014), “Nonuniform ACC circuit lower bounds”. Neither journal file was retrieved; no arXiv id appears in the 2001.07788 bibliography. Williams arXiv:1212.1891 lists typical classes as AC0, ACC0, TC0, NC1, NC, P/poly; B2-SIZE(O(n)) is not on that list, and usefulness there is against n^k-size C-circuits.

No P vs NP claim. Affine-disperser linear bounds are unchanged. Li-Yang STOC 2022 is still not file-retrieved.