On the solution‐space geometry of random constraint satisfaction problems
From MaRDI portal
Publication:5892482
DOI10.1002/rsa.20323zbMath1217.68156MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Unnamed Item, Unnamed Item, The solution space geometry of random linear equations, Solution-Graphs of Boolean Formulas and Isomorphism1, Disordered systems insights on computational hardness, Storage capacity in symmetric binary perceptrons, The solution space structure of planted constraint satisfaction problems with growing domains, On the connectivity of proper colorings of random graphs and hypergraphs, Homomorphism Reconfiguration via Homotopy, Walksat Stalls Well Below Satisfiability, Completeness Results for Counting Problems with Easy Decision, Unnamed Item, The condensation transition in random hypergraph 2-coloring, On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs, Free Energy Wells and Overlap Gap Property in Sparse PCA, Random \(\mathbb{Z}^d\)-shifts of finite type, The set of solutions of random XORSAT formulae, Generic properties of a computational task predict human effort and performance, Solution clustering in random satisfiability, Reconfiguration in bounded bandwidth and tree-depth, Constraining the clustering transition for colorings of sparse random graphs, Finding a large submatrix of a Gaussian random matrix, The overlap gap property in principal submatrix recovery, The number of solutions for random regular NAE-SAT, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length, Sparse high-dimensional linear regression. Estimating squared error and a phase transition, Completeness, approximability and exponential time results for counting problems with easy decision version, Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors, Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Solution-Graphs of Boolean Formulas and Isomorphism, On the concentration of the number of solutions of random satisfiability formulas, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, The Decimation Process in Random k-SAT, Random Instances of Problems in NP – Algorithms and Statistical Physics
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
