Hiding Quiet Solutions in Random Constraint Satisfaction Problems

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g., graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions and the easy-hard-easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid-glass-solid phenomenology.

• Publication year

  2009

• Venue

  Physical Review Letters

• Publication date

  2009-01-14

• Fields of study

  Medicine, Physics, Computer Science, Mathematics

• Identifiers
  DOI 10.1103/PhysRevLett.102.238701arXiv 0901.2130PMID 19658978
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Locked constraint satisfaction problems.

  2008cited by this paper
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

  2008cited by this paper
• Constraint satisfaction problems with isolated solutions are hard

  2008cited by this paper
• From one solution of a 3-satisfiability formula to a solution cluster: frozen variables and entropy.

  2008cited by this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cited by this paper
• On the Freezing of Variables in Random Constraint Satisfaction Problems

  2007cited by this paper
• Potts glass on random graphs

  2007cited by this paper
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• Hard Satisfiable Clause Sets for Benchmarking Equivalence Reasoning Techniques

  2006cited by this paper
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

  2006cited by this paper
• Landscape of solutions in constraint satisfaction problems

  2005cited by this paper
• Reconstruction on Trees and Spin Glass Transition

  2005cited by this paper
• Hiding Satisfying Assignments: Two Are Better than One

  2004cited by this paper
• Coloring random graphs

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Hiding solutions in random satisfiability problems: A statistical mechanics approach

  2001cited by this paper
• Metabolic engineering of plant alkaloid biosynthesis. Proc Natl Acad Sci U S A

  2001cited by this paper
• A ferromagnet with a glass transition

  2001cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper

• Eidolon: A Practical Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks

  2026cites this paper
• Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

  2026cites this paper
• Beyond-mean-field fluctuations for the solution of constraint satisfaction problems

  2025cites this paper
• Planted Solutions in Quantum Chemistry: Generating Non-Trivial Hamiltonians with Known Ground States.

  2025cites this paper
• Hybrid universality classes of systemic cascades

  2025cites this paper
• Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions

  2025cites this paper
• Improving Discrete Diffusion Unmasking Policies Beyond Explicit Reference Policies

  2025cites this paper
• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

  2024influential citation
• Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs

  2024cites this paper
• Assessing and advancing the potential of quantum computing: A NASA case study

  2024cites this paper
• Dense Hopfield Networks in the Teacher-Student Setting

  2024cites this paper
• Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs

  2024cites this paper
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems

  2023cites this paper
• Dynamics and fluctuations of minimally structured glass formers.

  2023cites this paper
• Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective

  2023cites this paper
• Generating hard Ising instances with planted solutions using post-quantum cryptographic protocols

  2023cites this paper
• Posiform Planting: Generating QUBO Instances for Benchmarking

  2023cites this paper
• The Copycat Perceptron: Smashing Barriers Through Collective Learning

  2023cites this paper
• Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

  2023cites this paper
• Planted vertex cover problem on regular random graphs and nonmonotonic temperature-dependence in the supercooled region.

  2023cites this paper
• Sparse random hypergraphs: Non-backtracking spectra and community detection

  2022cites this paper
• Equilibrium fluctuations in mean-field disordered models.

  2022cites this paper
• Creating bulk ultrastable glasses by random particle bonding

  2022cites this paper
• Collective dynamics in a glass-former with Mari-Kurchan interactions.

  2022cites this paper
• When you can’t count, sample!

  2022cites this paper
• Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

  2022cites this paper
• Disordered systems insights on computational hardness

  2022cites this paper
• Planted matching problems on random hypergraphs

  2022cites this paper
• A theory explaining the limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems

  2022influential citation
• Construction of Simplicial Complexes with Prescribed Degree-Size Sequences

  2021cites this paper
• Circumventing spin-glass traps by microcanonical spontaneous symmetry breaking.

  2021cites this paper
• Hiding solutions in model RB: Forced instances are almost as hard as unforced ones

  2021cites this paper
• Optimization of the dynamic transition in the continuous coloring problem

  2021cites this paper
• Local Dynamical Heterogeneity in Simple Glass Formers.

  2021cites this paper
• The solution space structure of planted constraint satisfaction problems with growing domains

  2021cites this paper
• On statistical inference when fixed points of belief propagation are unstable

  2021cites this paper
• Frozen 1‐RSB structure of the symmetric Ising perceptron

  2021cites this paper
• Computational phase transitions in sparse planted problems?

  2021cites this paper
• Unbiased Monte Carlo Cluster Updates with Autoregressive Neural Networks

  2021cites this paper
• Relaxation Dynamics in the Energy Landscape of Glass-Forming Liquids

  2021cites this paper
• Gradient descent dynamics in the mixed p-spin spherical model: finite-size simulations and comparison with mean-field integration

  2020cites this paper
• On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs

  2020cites this paper
• Deep Learning Quantum States for Hamiltonian Estimation

  2020cites this paper
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking

  2020cites this paper
• Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval

  2020cites this paper
• Strong Replica Symmetry in High-Dimensional Optimal Bayesian Inference

  2020cites this paper
• Thresholds of descending algorithms in inference problems

  2020cites this paper
• Approximate Network Symmetry.

  2020cites this paper
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

  2020cites this paper
• On Low Density Majority Codes Hajir Roozbehani

  2019cites this paper
• Computational Hardness of Certifying Bounds on Constrained PCA Problems

  2019cites this paper
• Storage capacity in symmetric binary perceptrons

  2019cites this paper
• Gardner physics in amorphous solids and beyond.

  2019cites this paper
• Wishart planted ensemble: A tunably rugged pairwise Ising model with a first-order phase transition.

  2019cites this paper
• Self-planting: digging holes in rough landscapes

  2019cites this paper
• On Low Density Majority Codes

  2019cites this paper
• Low density majority codes and the problem of graceful degradation

  2019cites this paper
• University of Birmingham On the Complexity of Random Satisfiability Problems with Planted Solutions

  2018cites this paper
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference

  2018cites this paper
• Estimating the density of states of frustrated spin systems

  2018cites this paper
• On the glassy nature of the hard phase in inference problems

  2018cites this paper
• Universality of the stochastic block model

  2018cites this paper
• Inférence et réseaux complexes

  2018cites this paper
• Detectability of macroscopic structures in directed asymmetric stochastic block model.

  2018cites this paper
• Detection limits and fluctuation results in some spiked random matrix models and pooling of discrete data

  2018influential citation
• Typology of phase transitions in Bayesian inference problems

  2018cites this paper
• Quantum algorithm for energy matching in hard optimization problems

  2018cites this paper
• The replica symmetric phase of random constraint satisfaction problems

  2018cites this paper
• C O ] 1 3 A ug 2 01 8 Rigid colourings of hypergraphs and contiguity

  2018cites this paper
• Thermalization, Freeze-out, and Noise: Deciphering Experimental Quantum Annealers

  2017cites this paper
• Numerics in the Mari-Kurchan Model

  2017cites this paper
• Charting the Replica Symmetric Phase

  2017cites this paper
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

  2017cites this paper
• Advantages of Unfair Quantum Ground-State Sampling

  2017cites this paper
• Structure-Preserving Instance Generation

  2016cites this paper
• The melting of stable glasses is governed by nucleation-and-growth dynamics.

  2016cites this paper
• On the Number of Solutions in Random Hypergraph 2-Colouring

  2016influential citation
• Mean-field message-passing equations in the Hopfield model and its generalizations.

  2016cites this paper
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds

  2016cites this paper
• Information-theoretic thresholds from the cavity method

  2016cites this paper
• Practical engineering of hard spin-glass instances

  2016cites this paper
• Learning and Intelligent Optimization

  2016influential citation
• Sparse Probabilistic Models - Phase Transitions and Solutions via Spatial Coupling

  2015cites this paper
• Detection of Planted Solutions for Flat Satisfiability Problems

  2015cites this paper
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel

  2015cites this paper
• Spectral detection in the censored block model

  2015cites this paper
• Statistical physics of inference: thresholds and algorithms

  2015cites this paper
• Limits of discrete distributions and Gibbs measures on random graphs

  2015cites this paper
• Numerical detection of the Gardner transition in a mean-field glass former.

  2015cites this paper
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates

  2015cites this paper
• Spectral detection on sparse hypergraphs

  2015cites this paper
• Phase Transitions in Discrete Structures

  2015cites this paper
• Statistical Physics of Inference and Bayesian Estimation

  2015cites this paper
• Following the evolution of glassy states under external perturbations: the full replica symmetry breaking solution

  2015cites this paper
• Following the evolution of metastable glassy states under external perturbations : compression and shear-strain

  2015cites this paper
• Statistical Physics of Inference problems

  2014cites this paper
• Hopping and the Stokes–Einstein relation breakdown in simple glass formers

  2014cites this paper
• Aspects of Statistical Physics in Computational Complexity

  2014cites this paper
• Solving the undirected feedback vertex set problem by local search

  2014cites this paper
• Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's

  2014cites this paper