文章基本信息

标题：Mansour’s Conjecture is True for Random DNF Formulas
本地全文：下载
作者：Adam Klivans ; Homin Lee ; Andrew Wan 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 \Ex01[(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 01n (for any constant error parameter). Applying recent work on sandwiching polynomials, our results imply that a t−O(log1) -biased distribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work