{"id":"openai-math/Variance-of-the-Random-k-SAT-Hitting-Time","pdf":"https://github.com/openai/math/blob/main/preprints/Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026/article.pdf","url":"https://github.com/openai/math/tree/main/preprints/Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026","tags":["random-sat","probability","combinatorics"],"score":0,"title":"Variance of the Random k-SAT Hitting Time","domain":"Probability and statistical mechanics","family":"235","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.PR","summary":"Let H n be the index of the first unsatisfiable prefix in random k -SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove $`\\mathop{\\mathrm{Var}}\\nolimits (H_n)=\\Theta_k(n)`$. For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of $`n\\log n`$; the companion paper on random 3-SAT sharpens this to $`\\Theta(n)`$. The same upper bounds proved here hold after clipping at any fixed positive multiple of n .","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{},"formalized":false,"family_title":"Limiting random SAT thresholds, sharp variance and computability"}