One-Shot Learning for k-SAT

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.