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-145 | 12th August 2026 02:56

The Scaling Window of Random $k$-SAT

RSS-Feed




TR26-145
Authors: Gaia Carenini
Publication: 16th August 2026 09:58
Downloads: 10
Keywords: 


Abstract:

We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random $k$-SAT is $O(n/\log n)$, improving the Friedgut-Bourgain bound of $O(n/\log\log n)$. We also show that random signed Not-All-Equal-$k$-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.



ISSN 1433-8092 | Imprint