Quiet Planting in the Locked Constraint Satisfaction Problems

Abstract

We study the planted ensemble of locked constraint satisfaction problems. We describe the connection between the random and planted ensembles. The use of the cavity method is combined with arguments from reconstruction on trees and first and second moment considerations; in particular the connection with the reconstruction on trees appears to be crucial. Our main result is the location of the hard region in the planted ensemble. In a part of that hard region instances have with high probability a single satisfying assignment.

21 pages, revised version

References in corpus (10)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Simple Glass Models and their Quantum Annealing
• Locked constraint satisfaction problems
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• A Lattice Model for Colloidal Gels and Glasses
• A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
• Message passing for the coloring problem: Gallager meets Alon and Kahale

Cited by in corpus (23)

• Statistical physics of inference: Thresholds and algorithms
• The method of moments and degree distributions for network models
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Finding One Community in a Sparse Graph
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Typology of phase transitions in Bayesian inference problems
• Storage capacity in symmetric binary perceptrons
• Disordered Systems Insights on Computational Hardness
• Spectral Detection on Sparse Hypergraphs
• Performance of simulated annealing in p-spin glasses
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Degeneracy, degree, and heavy tails in quantum annealing
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• (Dis)assortative Partitions on Random Regular Graphs
• Dense Hopfield Networks in the Teacher-Student Setting
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• The effect of quantum fluctuations on the coloring of random graphs
• The solution space structure of planted constraint satisfaction problems with growing domains
• Satisfiability Thresholds for Regular Occupation Problems
• Optimal sparse CDMA detection at high load
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates