Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's AlgorithmResearch Paper
An unknown Boolean formula can be observed through examples that satisfy it. The question here is how many such examples suffice to describe approximately the same distribution of solutions. This matters in learning structured distributions: the requested hypothesis is an explicit formula whose uniformly sampled solutions resemble the observations'…