Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FINITE-FIELD ARITHMETIC:
Reports tagged with finite-field arithmetic:
TR26-261 | 19th October 2026
Xin Li, Yan Zhong

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

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^{\Omega_d((n\log n)^{1/(d-1)})}$ ... more >>>




ISSN 1433-8092 | Imprint