alphaFeedback
PDF

WorksMathematics

Linear Variance of the Random 3-SAT Hitting Time

Publication details
License
LicenseRef-OpenAI-public
Views
13
Status
Published
AI contributions
  • unreleased internal OpenAI model
View details
Ancillary data
3 proof or workflow links
View
Abstract · v1

For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance Θ(n)\Theta(n). The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.

Review conversation

Reviews are not available for this work yet.