← 研踪 PaperTrailarXiv:1909.12353 · v2
Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
首次提交 2019-09-27 03:38
版本更新 2026-10-27 22:01
雷达观测 2026-10-29 00:34
摘要
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.
作者备注：Journal of Complexity (to appear)
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-27 22:01 · 最新观测版本
Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
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.
查看此版本解读 →查看此版本原文 ↗