# One-Shot Learning for k-SAT

arXiv: https://arxiv.org/abs/2502.07135 · HTML: https://mlsanity.com/paper/2502.07135/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 40 references that are in the map.
- First posted on arXiv 10 Feb 2025.

## Builds on (most cited first, 21 of 21)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Regression from Dependent Observations](https://mlsanity.com/paper/1905.03353/) (2019)
- [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models](https://mlsanity.com/paper/1901.07361/) (2019)
- [Hardness of parameter estimation in graphical models](https://mlsanity.com/paper/1409.3836/) (2014)
- [Optimal Single Sample Tests for Structured versus Unstructured Network Data](https://mlsanity.com/paper/1802.06186/) (2018)
- [Fast sampling and counting k-SAT solutions in the local lemma regime](https://mlsanity.com/paper/1911.01319/) (2019)
- [Logistic-Regression with peer-group effects via inference in higher order Ising models](https://mlsanity.com/paper/2003.08259/) (2020)
- [Deterministic counting Lov'asz local lemma beyond linear programming](https://mlsanity.com/paper/2212.14847/) (2022)
- [Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models](https://mlsanity.com/paper/1610.04317/) (2016)
- [Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models](https://mlsanity.com/paper/2004.10805/) (2020)
- [A Sampling Lov'asz Local Lemma for Large Domain Sizes](https://mlsanity.com/paper/2307.14872/) (2023)

## Abstract (arXiv)

Consider a k-SAT formula Phi where every variable appears at most d times. Let σ be a satisfying assignment, sampled proportionally to eβ m(σ) where m(σ) is the number of true variables and β is a real parameter. Given Phi and σ, can we efficiently learn β? This problem falls into a recent line of work about single-sample (``one-shot'') learning of Markov random fields. Our k-SAT setting was recently studied by Galanis, Kalavasis, Kandiros (SODA24). They showed that single-sample learning is possible when roughly d≤ 2k/6.45 and impossible when d≥ (k+1) 2k-1. In addition to the gap in~d, their impossibility result left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold for bounded-degree k-SAT formulas. 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 k2 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, obtaining significantly stronger bounds on d in terms of β. For the uniform case βrightarrow 0, we show that learning is possible under the condition dlesssim 2k/2. 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 dgtrsim 2k/2.