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