Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-158 | 22nd August 2026 18:30

Random 3-CNF formulas are hard for $k$-DNF resolution up to $k=O(\sqrt{\log n})$

RSS-Feed




TR26-158
Authors: Gaia Carenini
Publication: 30th August 2026 08:17
Downloads: 22
Keywords: 


Abstract:

We prove exponential lower bounds for $k$-DNF resolution on random $3$-CNF formulas throughout the range $k=O(\sqrt{\log n})$ at every constant clause density above the elementary first-moment bound for unsatisfiability. For random $3$-CNFs this improves Alekhnovich's range $k=O(\sqrt{\log n/\log\log n})$, and matches the $O(\sqrt{\log n})$ range obtained by Sofronova and Sokolov for random CNFs of sufficiently large constant width. We also obtain higher-density tradeoffs. In particular, random $3$-CNFs with $n\log^h n$ clauses are exponentially hard for $k=O(\sqrt{\log n/\log\log n})$ for every fixed $h>0$, while for every fixed $K$ the same conclusion holds simultaneously for all $1\le k\le K$ with $n^{1+\varepsilon}$ clauses whenever $\varepsilon<1/(4K^2+2)$.



ISSN 1433-8092 | Imprint