arXiv · Oct 19, 2026
Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness
By Xin Li, Yan Zhong
We give a short-description decomposition of bounded-width CNFs. For every fixed ε>0, every width-b CNF on m variables is an exact disjoint union of at most 2^(ε m) width-b CNFs, each determined by 2^(O_ε(b))log(m+1) satisfying assignments. For every fixed d≥3, we prove a worst-case size lower bound of 2^Ω_d((nlog n)^(1/(d-1))) against depth-at-most-d unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich–Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most S, where n≤ S≤2^c_dn^(1/(d-1)), has uniform sign correlation at most 2^-η_dnloglog S/(log S)^(d-1). Here c_d,η_d>0 depend only on d. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size 2^O(n^(2/3)) at depth eight and 2^(O(√ nlog n)) at depth nine. For every fixed integer h≥2, the construction gives depth-(4h+1) circuits of size 2^O_h(n^(1/h)log n). The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.