Minimizing energy below the glass thresholds

Abstract

Focusing on the optimization version of the random K-satisfiability problem, the MAX-K-SAT problem, we study the performance of the finite energy version of the Survey Propagation (SP) algorithm. We show that a simple (linear time) backtrack decimation strategy is sufficient to reach configurations well below the lower bound for the dynamic threshold energy and very close to the analytic prediction for the optimal ground states. A comparative numerical study on one of the most efficient local search procedures is also given.

12 pages, submitted to Phys. Rev. E, accepted for publication

References in corpus (10)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Survey propagation: an algorithm for satisfiability
• Typical random 3-SAT formulae and the satisfiability threshold
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• A backtracking survey propagation algorithm for K-satisfiability
• Approximate analysis of search algorithms with "physical" methods
• Some remarks on the survey decimation algorithm for K-satisfiability
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
• Threshold values of Random K-SAT from the cavity method

Cited by in corpus (9)

• Algorithmic barriers from phase transitions
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Glassy Phase of Optimal Quantum Control
• Lossy data compression with random gates
• Minimal contagious sets in random regular graphs
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes