Vi bevisar att någon submodulär funktion f : {0, 1} n → {0, 1,..., k} kan representeras som en pseudoBoolean 2k-DNF formel. Pseudo-Boolean DNFs är en naturlig generalisering av DNF representation för funktioner med heltal intervall. Varje term i en sådan formel har en tillhörande integral konstant. Vi visar att en analog av Håstads växlande lemma håller för pseudo-Boolean k-DNFs om alla konstanter i samband med villkoren i formeln begränsas. Detta gör att vi kan generalisera Mansours PAC-lärande algoritm för k-DNFs att pseudo-Boolean kDNFs, och därmed ger en PAC-lärande algoritm med medlemskap frågor under den enhetliga fördelningen för submodulära funktioner i formuläret f : {0, 1} n → {0, 1,..., k}. Vår algoritm körs i tid polynomial i n, k O (k log k/ på), 1/ på och log(1/δ) och fungerar även i den agnostiska inställningen. Det tidigare arbetet med att lära sig submodulära funktioner [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] innebär endast n O(k) frågekomplexitet för lärande submodulära funktioner i denna miljö, för fasta och δ. Vår inlärningsalgoritm innebär en egenskapstestare för submodularitet av funktioner f : {0, 1} n → {0,....., k} med frågekomplex polynomial i n för k = O((log n/ log log log n) 1/2 ) och konstant närhet parameter  på.
Raskhodnikova och Yaroslavtsev överväger att lära sig och testa submodulära funktioner som tar värden i intervallet {0, 1,...., k} (kallas pseudo-Boolean) REF.
Learning pseudo-Boolean k-DNF and Submodular Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}