On the solution-space geometry of random constraint satisfaction problems

DOI10.1145/1132516.1132537zbMath1301.68190OpenAlexW1980276492MaRDI QIDQ5891921

Federico Ricci-Tersenghi, Demetrios Achlioptas

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132537

zbMATH Keywords

satisfiabilitysurvey propagationrandom formulas

Mathematics Subject Classification ID

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 (37)

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Disordered systems insights on computational hardness ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Cryptographic hardness of random local functions. Survey ⋮ The asymptotics of the clustering transition for random constraint satisfaction problems ⋮ The algorithmic hardness threshold for continuous random energy models ⋮ Locally computable UOWHF with linear shrinkage ⋮ On the Boolean connectivity problem for Horn relations ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Finding one community in a sparse graph ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Random subcubes as a toy model for constraint satisfaction problems ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ⋮ Finite size scaling for the core of large random hypergraphs ⋮ Pairs of SAT-assignments in random Boolean formulæ ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Optimal testing for planted satisfiability problems ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ Solution clustering in random satisfiability ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ Gibbs measures and phase transitions on sparse random graphs ⋮ Statistical and algebraic analysis of a family of random Boolean equations ⋮ Pruning processes and a new characterization of convex geometries ⋮ Estimating satisfiability ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ The condensation transition in random hypergraph 2-coloring ⋮ The number of solutions for random regular NAE-SAT ⋮ Geometric properties of satisfying assignments of random ε-1-in-kSAT ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Minimal contagious sets in random regular graphs ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

This page was built for publication: On the solution-space geometry of random constraint satisfaction problems