All reports by Author Homin Lee:

__
TR11-090
| 2nd June 2011
__

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee#### Submodular Functions Are Noise Stable

Revisions: 2

__
TR10-023
| 23rd February 2010
__

Adam Klivans, Homin Lee, Andrew Wan#### Mansourâ€™s Conjecture is True for Random DNF Formulas

Revisions: 3

__
TR10-022
| 23rd February 2010
__

Vitaly Feldman, Homin Lee, Rocco Servedio#### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

__
TR07-129
| 25th October 2007
__

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan#### Learning Random Monotone DNF

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

Adam Klivans, Homin Lee, Andrew Wan

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 >>>

Vitaly Feldman, Homin Lee, Rocco Servedio

Much work has been done on learning various classes of ``simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>