Reconstruction and clustering in random constraint satisfaction problems

DOI10.1137/090755862MaRDI QIDQ3094944zbMATH OpenOpenAlexFDO

Authors Andrea Montanari, Ricardo L. Restrepo, Prasad Tetali

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.2751

zbMATH Keywords

message passing algorithmsrandom SATsharp threshold

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of natural technical conditions on a large family of (random) CSP's, and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSP's. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as, random instances of Not-All-Equal-SAT, k-XOR formulae, hypergraph 2-coloring, and graph k-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of problems with a similar threshold structure.

Recommendations

• Solution clustering in random satisfiability
• The set of solutions of random XORSAT formulae
• On the solution-space geometry of random constraint satisfaction problems
• The asymptotics of the clustering transition for random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems

Cited in

(37)

• Phase transitions in discrete structures
• Charting the replica symmetric phase
• Threshold saturation in spatially coupled constraint satisfaction problems
• The number of solutions for random regular NAE-SAT
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Optimal testing for planted satisfiability problems
• On the number of solutions in random hypergraph 2-colouring
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Unsatisfiability bounds for random CSPs from an energetic interpolation method
• Universal factor graphs
• Performance of sequential local algorithms for the random NAE-K-SAT problem
• Quiet planting in the locked constraint satisfaction problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Random instances of problems in NP -- algorithms and statistical physics
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Bounds for random constraint satisfaction problems via spatial coupling
• The replica symmetric phase of random constraint satisfaction problems
• Charting the replica symmetric phase
• Biased landscapes for random constraint satisfaction problems
• Satisfiability thresholds for regular occupation problems
• On the number of solutions in random graph \(k\)-colouring
• Planting colourings silently
• Frozen variables in random Boolean constraint satisfaction problems
• The condensation transition in random hypergraph 2-coloring
• A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
• The set of solutions of random XORSAT formulae
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• On the solution-space geometry of random constraint satisfaction problems
• Combinatorial statistics and the sciences
• Algorithmic obstructions in the random number partitioning problem
• Learning cluster-based structure to solve constraint satisfaction problems
• Frozen 1-RSB structure of the symmetric Ising perceptron
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Local geometry of NAE-SAT solutions in the condensation regime
• Reconstruction for the Potts model
• Local convergence of random graph colorings
• Gibbs measures and phase transitions on sparse random graphs

This page was built for publication: Reconstruction and clustering in random constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094944)