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 >>>

We give a $3.5n-o(n)$ lower bound on the size of Boolean circuits over the $B_2$ basis computing an explicit Boolean function F in P. This improves the best previous lower bound of $3.1n-o(n)$ [Li-Yang22].

The proof of the lower bound uses the gate elimination technique, and builds heavily on ideas ... more >>>

Michael O. Rabin was a major founder and leader of theoretical computer science. He died on April 14, 2026, at the age of 94. This paper aims to survey the wide scope and lasting impact of his research.

more >>>