papersTODAY 04:00 UTC
Study Tightens Sample Complexity Bounds for Valiant's CNF Learning Algorithm
Researchers revisit Valiant's 1984 algorithm for learning CNF formulas with bounded clause size and variable degree from uniformly random satisfying assignments. Working in the local lemma regime, they derive near-tight sample complexity guarantees under a stated condition relating clause size to variable degree. The work is a theoretical contribution to computational learning theory rather than a practical tool release.