Learning pseudo-Boolean k-DNF and Submodular Functions

Sofya Raskhodnikova, Grigory Yaroslavtsev

We prove that any submodular function f: {0,1}^n -> {0,1,...,k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF repre…