Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm

Gabriel Istrate, Cosmin Bonchis, Mircea Marin

We analyze the expected running time of WalkSAT, a well-known local search procedure for satisfiability solving, on satisfiable instances of the k-XOR SAT problem. We obtain estima…