Walksat Stalls Well Below Satisfiability

DOI10.1137/16M1084158zbMath1371.68109arXiv1608.00346MaRDI QIDQ5267998

Samuel Hetterich, Amin Coja-Oghlan, A. Haqshenas

Publication date: 14 June 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.00346

zbMATH Keywords

random \(k\)-SATWalksat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (11)

Computational barriers to estimation from low-degree polynomials ⋮ Counting Solutions to Random CNF Formulas ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Tractability from overparametrization: the example of the negative perceptron ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ The overlap gap property in principal submatrix recovery ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Optimal low-degree hardness of maximum independent set ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic \(k\)-SAT threshold
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Local algorithms for independent sets are half-optimal
• Analyzing Walksat on Random Formulas
• Proof of the Satisfiability Conjecture for Large k
• The large deviations of the whitening process in random constraint satisfaction problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• An improved exponential-time algorithm for k -SAT
• Analysing Survey Propagation Guided Decimation on Random Formulas
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Cores in random hypergraphs and Boolean formulas
• Theory and Applications of Satisfiability Testing
• On belief propagation guided decimation for random k-SAT
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Better Algorithm for Random k-SAT
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• Theory and Applications of Satisfiability Testing
• Frozen variables in random boolean constraint satisfaction problems
• Limits of local algorithms over sparse random graphs
• On the solution‐space geometry of random constraint satisfaction problems

This page was built for publication: Walksat Stalls Well Below Satisfiability