Mathematical remark

Discussion note on DeMorgan-formula and Karchmer-Wigderson methods versus the conjecture. File-verified source: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, Section 1 DeMorgan-formulas paragraph, Lemma 1.3, Section 1.2.3 / Open Problem 1.2, and the bibliography entries And87, Hås98, Tal14, KW90, KRW95, Nec66. Secondary record: Filmus-Meir-Tal arXiv:2012.02210v3 abstract (export.arxiv.org API XML; PDF retrieved as /work/library/filmus-meir-tal-2012.02210v3.pdf but TJ-encoded, so body claims below use only the abstract), Theory of Computing 19 (2023).

GKW record that DeMorgan formulas are out-degree-1 fan-in-2 AND/OR circuits with literals at the inputs; that explicit super-linear unrestricted circuit lower bounds are not known; and that both random-restriction shrinkage and Karchmer-Wigderson / KRW methods have led to L_DM >= n^{3-o(1)} and are stuck there. A DeMorgan formula is a special B2-circuit, so C_B2(f) <= L_DM(f). A lower bound on formula size does not lower-bound unrestricted circuit size.

Lemma 1.3 does not invert a single-formula bound. Every size-s B2 circuit equals an OR of 2^{ceil(s/3)} formulas of size < s. Forcing C(f) > 3n therefore requires that f is not equal to any OR of 2^n formulas of size < 3n. The recorded n^{3-o(1)} bound only says f is not itself a single small formula. If C(f) = 3n, Lemma 1.3 produces exactly such an OR, which is consistent with L_DM(f) being cubic or larger. GKW Section 1.3 already cites Nec66 as almost-quadratic single-formula bounds and treats hardness against an OR of << 2^n linear-size formulas as a different, open property.

GKW’s own formula depth reduction (Section 1.2.3, Open Problem 1.2) is aimed at improving formula lower bounds past cubic, conditionally on low-degree probabilistic polynomials for size-s DeMorgan formulas. That is the opposite direction from unrestricted B2 size. KW90 as cited is monotone depth for connectivity. KRW95 as cited is super-logarithmic depth via communication direct sum / formula composition. Even a full KRW resolution would multiply formula complexity and would remain in the formula model.

Later record, abstract only: Filmus-Meir-Tal 2012.02210v3 state that Håstad’s Õ(n^3) Andreev bound remains, up to lower-order improvements, the state-of-the-art explicit formula lower bound in that paper’s account, and they prove Õ(n^3) for an explicit function in AC0. AC0 subset P subset E, so that function is already an E-language with polynomial-size constant-depth unbounded-fan-in circuits. Compiling a size-n AC0 circuit with fan-in at most n yields B2-size at most n(n-1); that is an upper bound, not a omega(n) B2 lower bound, and FMT’s actual AC0 size was not extracted from the PDF. export.arxiv.org phrase search all:“formula size” AND all:Andreev AND all:cubic returned only this paper.

Finite bookkeeping: work/code/formula_kw_gap.py (executor). At n=64, n^3 = 262144 versus 3n = 192 (ratio 1365); Lemma 1.3 top fan-in is 2^{64}; a worst-case unfolding of a size-3n DAG has 2^{192} leaves. A cubic single-formula bound sits far below that unfolding upper bound and does not rule out the Lemma 1.3 OR.

Barriers: this is a model comparison, not oracle diagonalization. Natural-proof usefulness of an n^{3-o(1)} DeMorgan-formula property is against formulas, not against P/poly or B2-SIZE(O(n)). Algebrization of KW/KRW is not analysed here. No P versus NP claim. Affine-disperser linear bounds and the GKW combinatorial s_3^{16} / Open Problem 1.1 route are unchanged.