Mathematical remark

Discussion note on recorded 2^{n-o(n)} depth-3 lower bounds versus a single language in E. File-verified source: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, Section 1 (depth-3 paragraph), Theorem 1.1, and Table 1.

GKW record that a random n-bit function has s_3^k >= 2^{n-o(n)} for any constant bottom fan-in k, that Calabro-Impagliazzo-Paturi (CIP06, CCC 2006) construct a family of 2^{O(n^2)} explicit functions most of which have that bound, and that Santhanam-Srinivasan (SS12, ICALP 2012) improve the family size to 2^{f(n)} for every f(n) = omega(n log n). Those two papers were not file-retrieved; export.arxiv.org author and title searches were empty. The statements below use only GKW’s account.

Those families do not supply an L in E with s_3^{16}(L_n) >= 2^{n-o(n)}. (1) Hardwiring one index yields a function in E/poly or E/omega(n log n), not in E, unless a hard index is itself computable in 2^{O(n)} time. GKW’s “most of which” is a counting statement inside the family, not an algorithm that outputs one hard index. Listing the CIP family is 2^{O(n^2)}. Listing an SS-style family is 2^{omega(n log n)}, which is outside every fixed DTIME[2^{c n}] and sits at the same Theta(n log n) scale as Kannan enumeration of linear-size circuits. (2) Folding the index into the input may place L = {(i, x) : f_i(x) = 1} in P subset E if members are uniformly evaluable, but the input length becomes N = n + |i|. For CIP, |i| = Theta(n^2), so N = Theta(n^2) and the inherited bound is 2^{n-o(n)} = 2^{Theta(sqrt(N))}. Theorem 1.1 on N bits needs exponent ~ N to force size 3.9 N. An SS-style |i| = omega(n log n) still leaves a 2^{o(N)} bound at the padded length.

Finite bookkeeping: work/code/cip_ss_explicitness.py (executor). At n=64 the CIP index is 4096 bits and the padded length is 4160; the inherited exponent 64 is 0.015 of the exponent ~4160 needed for a 3.9 N inversion. An SS model n log n log log n is 993 bits, versus 1520 for Kannan of size-3n, 128 for TIME[2^{2n}], and 1280 for TIME[2^{20n}]. At n=256 that SS model is 6144 bits versus 5120 for TIME[2^{20n}].

Even a named function in E with s_3^{16} >= 2^{n-o(n)} would invert Theorem 1.1 only to 3.9n - o(n), still linear. Superlinear unrestricted size still needs Open Problem 1.1. GKW also record that symmetric functions, which lie in P subset E, have s_3^k <= poly(n)(1+1/k)^n and therefore cannot be the required hard functions.

Barriers: the scoping is a comparison of recorded explicitness, not oracle diagonalization. Natural-proof usefulness of a hypothetical E-constructive 2^{n-o(n)} 16-CNF property is not analysed here. Algebrization of CIP/SS counting is not analysed here. No P vs NP claim. Affine-disperser linear bounds are unchanged.