למידת יחידות CNF מפורטות מפתרונות אקראיים: עקביות ספיקר קרובה לאפס לאלגוריתם של וליאנט

תקציר מקורי באנגליתarXiv:2609.15268v1 Announce Type: new Abstract: We revisit Valiant's algorithm (Commun. ACM'84) for learning $n$-variable CNF formulas with clause size $k$ and variable degree $d$ from i.i.d. uniform random solutions in the local lemma regime. For fixed $t\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieves total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)$ sample complexity. For $t>1$, we prove a matching lower bound for Valiant's algorithm. At $t=1$ (covering $0<t<1$), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound $\widetilde\Omega(n/\varepsilon)$.