Submodular Functions Are Noise Stable

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari +1

We show that all non-negative submodular functions have high {\em noise-stability}. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to…