One-shot learning for k-SAT

Journal article

Consider a k-SAT formula $\Phi$ where every variable appears at most $d$ times, and let $\sigma$ be a satisfying assignment of $\Phi$ sampled proportionally to $e^{\beta m(\sigma)}$ where $m(\sigma)$ is the number of variables set to true and $\beta$ is a real parameter. Given $\Phi$ and $\sigma$, can we learn the value of $\beta$ 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, Kalavasis, Kandiros (SODA 2024). They showed that single-sample learning is possible when roughly $d \le 2^{k/6.45}$ and impossible when $d \ge (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 $\beta$ is sufficiently large, and bootstrap this to small values of $\beta$ when $d$ scales exponentially with $k$, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain stronger bounds on $d$ in terms of $\beta$. For the uniform case $\beta \to 0$, our analysis shows that learning is possible under the condition $d \lesssim 2^{k/2}$. This matches the sampling threshold up to constant factors, since sampling a uniformly-distributed satisfying assignment is NP-hard for $d \gtrsim 2^{k/2}$.

Authors: Galanis, A; Goldberg, LA; Zhang, X

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 307
• Article number: 105385
• Publication date: 2025-11-24
• Acceptance date: 2025-11-24
• DOI: 10.1016/j.ic.2025.105385
• EISSN: 1090-2651
• ISSN: 0890-5401
• Language: English
• Keywords: computational learning theory; maximum likelihood estimation; k-SAT