Showing 2024Show all
2 papers · 1 filter
math.CO2024
WalkSAT is linear on random 2-SAT
Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper +3
In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with variables in $…
math.CO2024
Random walks on edge colored random graphs
Colin Cooper, Alan Frieze
We consider random walks on edge coloured random graphs, where the colour of an edge reflects the cost of using it. In the simplest instance, the edges are coloured red or blue. Bl…