Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
arXiv:1909.12353
Abstract
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 estimates of this expected running time by reducing the problem to a setting amenable to classical techniques from drift analysis. A crucial ingredient of this reduction is the definition of (new, explosive) hypergraph versions of interacting particle systems, notably of coalescing and annihilating random walks as well as the voter model. The use of these tools allows to show that the expected running time of WalkSAT depends on structural parameter (we call odd Cheeger drift) of the dual of the formula hypergraph.
arXiv commentJournal of Complexity (to appear)
References in corpus (5)
- Social Balance on Networks: The Dynamics of Friendship and Enmity
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT