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

Xin Li, Yan Zhong

We give a short-description decomposition of bounded-width CNFs. For every fixed $\epsilon >0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\va…