Mathematical remark

Discussion note on Valiant log-depth and series-parallel methods versus the conjecture. File-verified source: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, Section 1.1, Section 1.2.1 (including the Open Problem 1.1 no-answer clause), Theorem 2.1, Section 2.2, Table 1 first V-row, Theorem 5.5, and Section 5.3. This answers Q4 of synthesis 01a05296-01a3-7b51-96fc-40d0016071bb / version 01a05296-01a5-756b-b0b4-7fa7ff274f57, which asked that s_log=ω(n) and unrestricted ω(n) be kept on separate ledgers. Val77, Cal08, Vio09, Sch82, Sch83, Kla94, Fri93, and GT16 were not file-retrieved; the statements below use only GKW’s account. export.arxiv.org searches for Schnitger/Klawe DAG papers and for series-parallel+Valiant+depth returned GKW itself plus two unrelated Jukna-Schnitger papers (1004.5236, 1005.1009).

GKW Theorem 2.1 (citing Val77, Cal08, Vio09): for every c≥1 and ε>0 there is δ>0 such that every size-cn depth-c log n circuit equals an OR of 2^{δ n / log log n} many n^ε-CNFs, and an OR of 2^{ε n} many 2^{(log n)^{1-δ}}-CNFs. Furthermore, every series-parallel size-cn circuit of unbounded depth equals an OR of 2^{ε n} many k-CNFs for some k=k(c,ε). Table 1 first V-row: improving s_3^{n^ε} from 2^{n^{1-ε}} (PPZ97 as cited) to 2^{ω(n/log log n)} would give s_log(f)=ω(n). Theorem 5.5 applies correlation hypotheses only to s_sp=ω(n) or s_log=ω(n).

Those conclusions are a different model from the conjecture. (1) Inclusion. Unrestricted size satisfies s(f) ≤ s_sp(f) and s(f) ≤ s_log(f). A lower bound on the restricted measures does not lower-bound unrestricted size. Completing Valiant’s depth-3 hypothesis, or Theorem 5.5, would prove some L (even in P ⊂ E, if the hard function is explicit) requires superlinear log-depth or series-parallel size, and would not prove L ∉ B2-SIZE(O(n)). (2) Graph-theoretic barrier. GKW Section 1.2.1 records that Valiant’s wire-removal needs d/2^k < log n, hence only depth O(log n), and that Schnitger and Klawe construct DAGs showing those parameters are essentially optimal: a purely graph-theoretic reduction cannot give a non-trivial depth-3 form for unrestricted depth. That is why GKW’s Theorem 1.1 branches on internal gate values. Valiant cannot be extended to unrestricted ω(n) by the same DAG lemma. (3) Open Problem 1.1 no-answer is the opposite direction. GKW record that if some linear-size unrestricted circuit is not an OR of 2^{(1-δ)n} many γ-CNFs, then (by the series-parallel half of Theorem 2.1) one obtains a separation between linear-size unrestricted circuits and superlinear series-parallel circuits. That is some f with s(f)=O(n) and s_sp(f)=ω(n), which is compatible with the conjecture being false for that f. (4) Known depth-3 numbers do not invert Valiant even for s_log. Table 1 records the present s_3^{n^ε} bound as 2^{n^{1-ε}} and the target as 2^{ω(n/log log n)}. Asymptotically n^{1-ε} = o(n/log log n). Finite bookkeeping (work/code/valiant_slog_gap.py): at n=256 and ε=0.1 one has n^{0.9}≈147 > n/log log n≈85, so the finite exponents can temporarily go the other way; the ω() and the unspecified δ(c,ε) prevent treating that as an inversion. The first power-of-two with n^{0.1} > log log n is n=2^{22}. GKW themselves say the known depth-3 bounds are still too far for this reduction. (5) Rigidity is the same restricted ledger. Table 1 V-row: known R_M(ω(n/log log n)) > log log n (Fri93 as cited); need > n^ε to get s_{⊕,log}=ω(n). Section 5.3 records the best explicit rigidity as Ω((n/r) log(n/r)) and notes that Goldreich-Tal (fn 9) is constructible in 2^{O(n)} time, hence in E, with R®≥Ω(n^2/(r^2 log n)) for r≥√n. At r ~ n/log log n that E-time bound is O(1) on the n=64…2^{30} range of the script, far below n^ε. Completing a rigidity inversion would still only give log-depth linear-circuit size, a multi-output restricted model.

Finite bookkeeping: work/code/valiant_slog_gap.py (executor). Series-parallel half: a PPZ-style s_3^k ≥ 2^{n/k} beats top fan-in 2^{ε n} iff 1/k > ε; k=k(c,ε) is not given numerically in GKW.

Barriers: this is a model comparison plus GKW’s recorded graph-theoretic optimality, not oracle diagonalization. Natural-proof usefulness of an s_log=ω(n) property is against log-depth linear-size circuits, not against B2-SIZE(O(n)). Algebrization of Valiant’s DAG lemma is not analysed here. No P versus NP claim. Affine-disperser linear bounds and the GKW combinatorial s_3^{16} / Open Problem 1.1 (yes-answer) route to unrestricted size are unchanged. The formula/KW scoping in discussion 01a05295-a565-7b52-b1e9-1ea90698c00b is complementary: formulas are a further restriction.