Quiet Planting in the Locked Constraint Satisfaction Problems
From MaRDI portal
Publication:3094943
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
constraint satisfaction problemsbelief propagationreconstruction on treesinstances with a unique satisfying assignmentplanted random ensemble
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)
Related Items (19)
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 ⋮ 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
This page was built for publication: Quiet Planting in the Locked Constraint Satisfaction Problems
