Variance of the Random k-SAT Hitting Time
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 .
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Variance-of-the-Random-k-SAT-Hitting-Time
curl -X POST /api/v1/records/openai-math/Variance-of-the-Random-k-SAT-Hitting-Time/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Variance-of-the-Random-k-SAT-Hitting-Time/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'