Quiet Planting in the Locked Constraint Satisfaction Problems

DOI10.1137/090750755zbMath1228.90101arXiv0902.4185OpenAlexW1782581930WikidataQ59460116 ScholiaQ59460116MaRDI QIDQ3094943

Lenka Zdeborová, Florent Krzakala

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/0902.4185

zbMATH Keywords

constraint satisfaction problemsbelief propagationreconstruction on treesinstances with a unique satisfying assignmentplanted random ensemble

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

Related Items (20)

Colouring graphs with forbidden bipartite subgraphs ⋮ Disordered systems insights on computational hardness ⋮ Storage capacity in symmetric binary perceptrons ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Finding one community in a sparse graph ⋮ An introduction to machine learning: a perspective from statistical physics ⋮ Planting Colourings Silently ⋮ The method of moments and degree distributions for network models ⋮ Random subcubes as a toy model for constraint satisfaction problems ⋮ Unnamed Item ⋮ Local convergence of random graph colorings ⋮ Dense Hopfield networks in the teacher-student setting ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds ⋮ (Dis)assortative partitions on random regular graphs

Uses Software

• Walksat

This page was built for publication: Quiet Planting in the Locked Constraint Satisfaction Problems