Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with submodularity:
TR11-090 | 2nd June 2011
Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

Submodular Functions Are Noise Stable

Revisions: 2

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

ISSN 1433-8092 | Imprint