To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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