pith. sign in

arxiv: 0902.4185 · v3 · pith:3QDXDWNNnew · submitted 2009-02-24 · ❄️ cond-mat.stat-mech · cond-mat.dis-nn· cs.CC

Quiet Planting in the Locked Constraint Satisfaction Problems

Lenka Zdeborov\'a , Florent Krzakala This is my paper
classification ❄️ cond-mat.stat-mech cond-mat.dis-nncs.CC
keywords plantedconnectionconstraintensemblehardlockedproblemsreconstruction
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Explaining Machine Learning and Memorization with Statistical Mechanics

    cs.LG 2026-06 unverdicted novelty 3.0

    Thesis uses statistical mechanics to study DAM and RBM models for understanding memorization, low-dimensional learning, and adversarial robustness in neural networks.