Hiding Quiet Solutions in Random Constraint Satisfaction Problems

Abstract

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.

4 pages, 3 figures

References in corpus (16)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Coloring random graphs
• Reconstruction on trees and spin glass transition
• A ferromagnet with a glass transition
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Landscape of solutions in constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Potts Glass on Random Graphs
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy

Cited by in corpus (87)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• Probing for quantum speedup in spin glass problems with planted solutions
• Hopping and the Stokes-Einstein relation breakdown in simple glass formers
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Social Influences in Opinion Dynamics: the Role of Conformity
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Quantum Annealing Correction with Minor Embedding
• Information-theoretic thresholds from the cavity method
• Dynamical transition of glasses: from exact to approximate
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Numerical detection of the Gardner transition in a mean-field glass former
• Following the evolution of glassy states under external perturbations: the full replica symmetry breaking solution
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Random Pinning Glass Transition: Hallmarks, Mean-Field Theory and Renormalization Group Analysis
• Typology of phase transitions in Bayesian inference problems
• Quantum algorithm for energy matching in hard optimization problems
• Storage capacity in symmetric binary perceptrons
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• Equilibrium ultrastable glasses produced by random pinning
• Unbiased Monte Carlo Cluster Updates with Autoregressive Neural Networks
• Relaxation dynamics in the energy landscape of glass-forming liquids
• Disordered Systems Insights on Computational Hardness
• Charting the replica symmetric phase
• Spectral Detection on Sparse Hypergraphs
• The hard-core model on random graphs revisited
• The melting of stable glasses is governed by nucleation-and-growth dynamics
• Performance of simulated annealing in p-spin glasses
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Universality of the stochastic block model
• Practical engineering of hard spin-glass instances
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Gradient descent dynamics in the mixed $p$-spin spherical model: finite size simulation and comparison with mean-field integration
• Creating bulk ultrastable glasses by random particle bonding
• Glassy nature of the hard phase in inference problems
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Advantages of Unfair Quantum Ground-State Sampling
• Local dynamical heterogeneity in glass formers
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Spectral Detection in the Censored Block Model
• Statistical Mechanics of Dictionary Learning
• Solving the undirected feedback vertex set problem by local search
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Limits of discrete distributions and Gibbs measures on random graphs
• Equilibrium Fluctuations in Mean-field Disordered Models
• Estimating the Density of States of Frustrated Spin Systems
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Parallel Tempering for the planted clique problem
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Solution space structure of random constraint satisfaction problems with growing domains
• Planting colourings silently
• Deep learning Local Reduced Density Matrices for Many-body Hamiltonian Estimation
• Following states in temperature in the spherical s+p-spin glass model
• The replica symmetric phase of random constraint satisfaction problems
• Calorimetric glass transition in a mean field theory approach
• Dense Hopfield Networks in the Teacher-Student Setting
• Thresholds of descending algorithms in inference problems
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Collective dynamics in a glass-former with Mari-Kurchan interactions
• When you can't count, sample! Computable entropies beyond equilibrium from basin volumes
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Optimization of the dynamic transition in the continuous coloring problem
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Dynamics and fluctuations of minimally-structured glass formers
• Low density majority codes and the problem of graceful degradation
• Realizing interdependent couplings as thermal or higher-order interactions
• Self-planting: digging holes in rough landscapes
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• The solution space structure of planted constraint satisfaction problems with growing domains
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• Approximate Network Symmetry
• Parallel Complexity of Random Boolean Circuits
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Planted matching problems on random hypergraphs
• Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
• Rigid colourings of hypergraphs and contiguity
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
• Construction of simplicial complexes with prescribed degree-size sequences
• On Low Density Majority Codes
• Hiding solutions in model RB: Forced instances are almost as hard as unforced ones