Mansour's Conjecture is True for Random DNF Formulas
Adam R. Klivans, Homin K. Lee, Andrew Wan · 2010
In 1994, Y. Mansour conjectured that for every DNF formula on n variables with t terms there exists a polynomial p with tO(log(1/)) non-zero coefficients such that Ex∈{0,1}n [(p(x) − f(x))2] ≤ . We make the first progress on this conjecture and show that it is true for several natural subclasses of DNF formulas including randomly chosen DNF formulas and read-k DNF formulas for constant k. Our result yields the first polynomial-time query algorithm for agnostically learning these subclasses of DNF formulas with respect to the uniform distribution on {0, 1}n (for any constant error parameter). Applying recent work on sandwiching polynomials, our results imply that a t−O(log 1/)-biased dis-tribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work. 1