{"id":"arxiv/2610.27127","url":"https://arxiv.org/abs/2610.27127","tags":["cs.CC","math.CO"],"score":0,"title":"Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness","domain":"cs.CC","source":"arxiv","authors":["Xin Li","Yan Zhong"],"reviews":0,"subject":"cs.CC","summary":"We give a short-description decomposition of bounded-width CNFs. For every fixed $\\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\\varepsilon(b)}\\log(m+1)$ satisfying assignments. For every fixed $d\\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\\log 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-19","reactions":{}}