Answers are grounded in this paper and cite their sources.
Consider a k -SAT formula Φ where every variable appears at most d times, and let σ be a satisfying assignment of Φ sampled proportionally to e β m ( σ ) where m ( σ ) is the number of variables set to true and β is a real parameter. Given Φ and σ , can we learn the value of β efficiently? This problem falls into a recent line of works about single-sample (“one-shot”) learning of Markov random fields. The k -SAT setting we consider here was recently studied by Galanis, A., Kalavasis, A., Kandiros, A.V., 2024. Learning hard-constrained models with one sample. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3184–3196. They showed that single-sample learning is possible when roughly d ≤ 2 k / 6.45 and impossible when d ≥ ( k + 1 ) 2 k − 1 . Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in d , left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of k -SAT formulas of bounded degree. Our main contribution is to answer this question negatively. We show that one-shot learning for k -SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees d as low as k 2 when β is sufficiently large, and bootstrap this to small values of β when d scales exponentially with k , via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on d in terms of β . In particular, for the uniform case β → 0 that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition d ≲ 2 k / 2 . Note that this is (up to constant factors) all the way to the sampling threshold – it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for d ≳ 2 k / 2 .
No takes yet. Share an insight, caveat, or question.
Galanis et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: