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-229 | 5th October 2026 11:17

A polynomial scaling window for random $k$-SAT and a proof of the satisfiability conjecture

RSS-Feed




TR26-229
Authors: Gaia Carenini
Publication: 5th October 2026 17:04
Downloads: 355
Keywords: 


Abstract:

We prove that the scaling window of random $k$-SAT has width $O(n^{1/2+1/k})$, a polynomial improvement over our previous bound of $O(n/\log n)$. Combined with a result of Abbe and Montanari, this establishes the satisfiability conjecture for every fixed $k\geq 3$.



ISSN 1433-8092 | Imprint