2012/08/10 by Sofya Raskhodnikova, Raskhodnikova, Sofya, Grigory Yaroslavtsev +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.DM #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.1208.2294
arxiv created 2012/08/10 · openalex publication_date 2012/08/10 · arxiv updated 2012/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that any submodular function f: 0,1n -> 0,1,...,k can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Hastad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f:0,1n -> 0,1,...,k. Our algorithm runs in time polynomial in n, kO(k log k / ε), 1/εand log(1/δ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] implies only nO(k) query complexity for learning submodular functions in this setting, for fixed epsilon and delta. Our learning algorithm implies a property tester for submodularity of functions f:0,1n -> 0, ..., k with query complexity polynomial in n for k=O((log n/ \loglog n)1/2) and constant proximity parameter ε.