Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MANSOUR:
Reports tagged with Mansour:
TR10-023 | 23rd February 2010
Adam Klivans, Homin Lee, Andrew Wan

#### Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

ISSN 1433-8092 | Imprint