Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness
Abstract
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 2Oε(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≤2cdn1/(d−1), has uniform sign correlation at most 2−ηdnloglog S/(log S)d−1. Here cd,η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 2O(n2/3) at depth eight and 2O(√nlog n) at depth nine. For every fixed integer h≥2, the construction gives depth-(4h+1) circuits of size 2Oh(n1/hlog n). The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.
Related
- One-dimensional quantum Gibbs states in constant circuit depth
- A Uniqueness theorem for the Vortex-Wave system with non-constant vorticity near the point vortex
- A non-lattice periodic point set beating the optimal lattice packing-covering constant in dimension five
- Reconstructing constant point heat sources from few temperature sensors: sparse selection and spatial resolution
- Stronger Spectral Bound for Clique Number
BibTeX
@misc{li2026short,
title = {{Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness}},
author = {Xin Li and Yan Zhong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27127},
eprint = {2610.27127},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27127},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness
AU - Xin Li
AU - Yan Zhong
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27127
UR - https://arxiv.org/abs/2610.27127
AB - 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/hlog n). The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.
ER -