notesum.ai

Published at December 5

WalkSAT is linear on random 2-SAT

math.CO
cs.DM
68Q87, 60C05

Released Date: December 5, 2024

Authors: Petra Berenbrink1, Amin Coja-Oghlan2, Colin Cooper3, Thorsten Götte1, Lukas Hintze1, Pavel Zakharov2

Aff.: 1University of Hamburg; 2TU Dortmund; 3King's College, University of London

Arxiv: http://arxiv.org/pdf/2412.04156v1