Performance of sequential local algorithms for the random NAE-K-SAT problem
From MaRDI portal
Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
Recommendations
Cites work
- A better algorithm for random \(k\)-SAT
- A new look at survey propagation and its generalizations
- Analysing survey propagation guided decimationon random formulas
- Average Case Complete Problems
- Catching the \(k\)-NAESAT threshold
- Gibbs states and the set of solutions of random constraint satisfaction problems
- scientific article; zbMATH DE number 3574966 (Why is no real title available?)
- Information, Physics, and Computation
- Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
- Limits of local algorithms over sparse random graphs
- Limits of locally-globally convergent graph sequences
- Local algorithms for independent sets are half-optimal
- On belief propagation guided decimation for random k-SAT
- On the solution-space geometry of random constraint satisfaction problems
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Reconstruction and clustering in random constraint satisfaction problems
- Survey propagation: An algorithm for satisfiability
- Two‐coloring random hypergraphs
Cited in
(28)- The overlap gap property in principal submatrix recovery
- Optimization of mean-field spin glasses
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- The overlap gap property and approximate message passing algorithms for \(p\)-spin models
- Suboptimality of local algorithms for a class of max-cut problems
- On the complexity of random satisfiability problems with planted solutions
- The replica symmetric phase of random constraint satisfaction problems
- Biased landscapes for random constraint satisfaction problems
- Information-theoretic and algorithmic thresholds for group testing
- Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
- 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
- Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
- A review on quantum approximate optimization algorithm and its variants
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- On perfectly friendly bisections of random graphs
- The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
- Tight Lipschitz hardness for optimizing mean field spin glasses
- Quantum glassiness from efficient learning
- Limits of sequential local algorithms on the random k-XORSAT problem
- Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms
- Shattering in the Ising p-spin glass model
- A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
- Binary perceptron computational gap: a parametric fl-RDT view
- Sharp phase transitions for the overlap gap property
- Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT
- Parametric RDT approach to computational gap of symmetric binary perceptron
This page was built for publication: Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968165)
