ECCC-Report TR10-023https://eccc.weizmann.ac.il/report/2010/023Comments and Revisions published for TR10-023en-usTue, 04 May 2010 22:26:13 +0300
Revision 3
| Mansour’s Conjecture is True for Random DNF Formulas |
Adam Klivans,
Homin Lee,
Andrew Wan
https://eccc.weizmann.ac.il/report/2010/023#revision3In 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 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/\epsilon)}$-biased distribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work.Tue, 04 May 2010 22:26:13 +0300https://eccc.weizmann.ac.il/report/2010/023#revision3
Revision 2
| Mansour’s Conjecture is True for Random DNF Formulas |
Adam Klivans,
Homin Lee,
Andrew Wan
https://eccc.weizmann.ac.il/report/2010/023#revision2In 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 randomly chosen DNF formulas and read-once DNF formulas.
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/\epsilon)}$-biased distribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work.
Fri, 02 Apr 2010 21:05:21 +0300https://eccc.weizmann.ac.il/report/2010/023#revision2
Revision 1
| Mansour’s Conjecture is True for Random DNF Formulas |
Adam Klivans,
Homin Lee,
Andrew Wan
https://eccc.weizmann.ac.il/report/2010/023#revision1In 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 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/\epsilon)}$-biased distribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work.Thu, 04 Mar 2010 15:46:04 +0200https://eccc.weizmann.ac.il/report/2010/023#revision1
Paper TR10-023
| Mansour’s Conjecture is True for Random DNF Formulas |
Adam Klivans,
Homin Lee,
Andrew Wan
https://eccc.weizmann.ac.il/report/2010/023In 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 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/\epsilon)}$-biased distribution fools the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work.Tue, 23 Feb 2010 21:52:11 +0200https://eccc.weizmann.ac.il/report/2010/023