On the solution‐space geometry of random constraint satisfaction problems
From MaRDI portal
Publication:5892482
DOI10.1002/rsa.20323zbMath1217.68156OpenAlexW2069603099MaRDI QIDQ5892482
Federico Ricci-Tersenghi, Amin Coja-Oghlan, Demetrios Achlioptas
Publication date: 11 May 2011
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.341.7377
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (41)
Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Generic properties of a computational task predict human effort and performance ⋮ Completeness Results for Counting Problems with Easy Decision ⋮ Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ Disordered systems insights on computational hardness ⋮ Storage capacity in symmetric binary perceptrons ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Random \(\mathbb{Z}^d\)-shifts of finite type ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ On the concentration of the number of solutions of random satisfiability formulas ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Shattering versus metastability in spin glasses ⋮ Optimizing mean field spin glasses with external field ⋮ Interactions of computational complexity theory and mathematics ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ On the connectivity of proper colorings of random graphs and hypergraphs ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs ⋮ The Decimation Process in Random k-SAT ⋮ Finding a large submatrix of a Gaussian random matrix ⋮ Constraining the clustering transition for colorings of sparse random graphs ⋮ Solution clustering in random satisfiability ⋮ Unnamed Item ⋮ ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors ⋮ Unnamed Item ⋮ Homomorphism Reconfiguration via Homotopy ⋮ The set of solutions of random XORSAT formulae ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ The solution space geometry of random linear equations ⋮ The overlap gap property in principal submatrix recovery ⋮ The condensation transition in random hypergraph 2-coloring ⋮ The number of solutions for random regular NAE-SAT ⋮ Unnamed Item ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Walksat Stalls Well Below Satisfiability ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
Cites Work
- Pairs of SAT-assignments in random Boolean formulæ
- Selecting Complementary Pairs of Literals
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Hunting for sharp thresholds
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Random Formulas Have Frozen Variables
- Gibbs states and the set of solutions of random constraint satisfaction problems
This page was built for publication: On the solution‐space geometry of random constraint satisfaction problems
