Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem

DOI10.1137/140989728zbMath1388.60037OpenAlexW2593370540MaRDI QIDQ2968165

David Gamarnik, Madhu Sudan

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140989728

zbMATH Keywords

algorithmsrandom graphsstatistical physics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Related Items (13)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Optimizing mean field spin glasses with external field ⋮ 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 ⋮ Unnamed Item ⋮ The overlap gap property in principal submatrix recovery ⋮ Optimization of mean-field spin glasses ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion

Cites Work

• Unnamed Item
• Local algorithms for independent sets are half-optimal
• Limits of locally-globally convergent graph sequences
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• A new look at survey propagation and its generalizations
• Information, Physics, and Computation
• Average Case Complete Problems
• Two‐coloring random hypergraphs
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Survey propagation: An algorithm for satisfiability
• On belief propagation guided decimation for random k-SAT
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• A Better Algorithm for Random k-SAT
• Catching the k-NAESAT threshold
• On the solution‐space geometry of random constraint satisfaction problems
• Limits of local algorithms over sparse random graphs

This page was built for publication: Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem