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 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,1 ^n -> 0,1,...,k . Our algorithm runs in time polynomial in n, k^ O(k 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 n^ O(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,1 ^n -> 0, ..., k with query complexity polynomial in n for k=O(( n n)^ 1 2 ) and constant proximity parameter .
Convex and submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and submodularity in two dimensions. The latter type of functions are equivalent to the well-known Monge matrices. A matrix @math is called a Monge matrix if for every @math and @math we have @math . If inequality holds in the opposite direction, then V is an inverse Monge matrix (supermodular function). Many problems, such as the traveling salesperson problem and various transportation problems, can be solved more efficiently if the input is a Monge matrix. In this work we present testing algorithms for the above properties. A testing algorithm for a predetermined property @math is given query access to an unknown function f and a distance parameter @math . The algorithm should accept f with high probability if it has the property @math and reject it with high probability if more than an @math -fraction of the function values should be modified so that f obtains the property. Our algorithm for testing whether a 1-dimensional function @math is convex (concave) has query complexity and running time of @math . Our algorithm for testing whether an n1 × n2 matrix V is a Monge (inverse Monge) matrix has query complexity and running time of @math . We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds. For the problem of testing whether a boolean function is k-linear (a parity function on k variables), we achieve a lower bound of Omega(k) queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as k-juntas. For some classes, such as the class of monotone functions and the class of s-sparse GF(2) polynomials, we significantly strengthen the best known bounds. We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function?