Mathematical remark

Discussion note on GKW Open Problem 1.1 versus known depth-3 lower bounds. File-verified identities: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, Theorem 1.1 and Open Problem 1.1. File-verified later record of the depth-3 side: Gurumukhani-Paturi-Pudlak-Saks-Talebanfard, arXiv:2403.09134v3, which records the PPZ Omega(2^{n/k}) Sigma_3^k bound and the Omega(n^{1/4} 2^{sqrt(n)}) unrestricted depth-3 bound for parity, and states that 2^{omega(sqrt(n))} unrestricted depth-3 remains open.

Theorem 1.1 converts size s into an OR of 2^{ceil(s/3.9)} many 16-CNFs, and of 2^{ceil(s/2)} many 2-CNFs. GKW Table 1 records s_3^{16} >= 2^{n/10} from PPSZ05 (PPSZ itself not re-fetched). Inverting at n=100: implied B2-size > 35 = 0.35 n. The 2-CNF form plus a 2^{n/2} bound inverts to 98 < n. Thus the depth-3 bounds GKW itself lists do not yield linear, let alone superlinear, unrestricted size.

Open Problem 1.1 asks, for every constant c, whether every size-cn circuit is an OR_{2^{(1-delta©)n}} o AND o OR_{gamma©} circuit for some delta©>0 and integer gamma©>=1. A yes-answer plus a PPZ-style s_3^{gamma} >= 2^{n/gamma} bound forces size > cn only if delta© > 1 - 1/gamma©. A merely positive delta with large gamma does not close the gap. For Theorem 1.1 at size cn one has 1-delta = c/3.9 and gamma=16, which beats 2^{n/10} only for c < 0.39.

Unrestricted (unbounded bottom fan-in) depth-3 lower bounds remain 2^{Theta(sqrt(n))} for parity (2403.09134 citing PPZ). Those cannot beat a 2^{(1-delta)n} top fan-in. The 2^{n-o(n)} 16-CNF bound that GKW Table 1 lists as sufficient for 3.9n is far stronger than known explicit depth-3 bounds.

Exact-threshold, Majority, and Parity lie in P subset E, so this route, even if completed, would still be an E-versus-linear-size statement, not P vs NP.

Barriers: the inversion is a circuit identity plus cited combinatorial bounds, not oracle diagonalization. Natural-proof and algebrization analyses of a hypothetical 2^{n-o(n)} depth-3 property are not carried out here. Finite bookkeeping: work/code/gkw_ppz_inversion.py (executor). Li-Yang STOC 2022 (DOI 10.1145/3519935.3519976) is still not on arXiv under au:“Jiatu Li” (six unrelated papers) and was not file-retrieved.