WorksMathematics
Linear Variance of the Random 3-SAT Hitting Time
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 . 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.