betaFeedback

WorksComputer Science

Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNF

Abstract

We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser–Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with mm clauses and at most two occurrences per variable, both algorithms terminate in O(m)O(m) expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require 2Θ(m)2^{Θ(\sqrt{m})} expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in O(m4)O(m^4) expected flips, whereas MT requires 2Ω(m)2^{Ω(m)} expected resampling steps. On another, MT terminates in O(m)O(m) expected resampling steps, whereas WalkSAT requires 2Ω(m)2^{Ω(m)} expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

Paper details

vlnc:W_g7qr2ja3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…