In this manuscript, we offer a gentle review of submodularity and supermodularity and their
properties. We offer a plethora of submodular definitions; a full description of a number of …

We consider the parallel complexity of submodular function minimization (SFM). We provide
a pair of methods which obtain two new query versus depth trade-offs a submodular function …

Despite the rich existing literature about minimax optimization in continuous settings, only
very partial results of this kind have been obtained for combinatorial settings. In this paper …

Graph sparsification underlies a large number of algorithms, ranging from approximation
algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its …

Optimization problems often involve vector norms, which has led to extensive research on
developing algorithms that can handle objectives beyond the $\ell_p $ norms. Our work …

We provide a generic technique for constructing families of submodular functions to obtain
lower bounds for submodular function minimization (SFM). Applying this technique, we …

Submodular function minimization is well studied, and existing algorithms solve it exactly or
up to arbitrary accuracy. However, in many applications, such as structured sparse learning …

In this paper we study the problem of minimizing a submodular function f:2^V→R that is
guaranteed to have a k-sparse minimizer. We give a deterministic algorithm that computes …

Minimizing the difference of two submodular (DS) functions is a problem that naturally
occurs in various machine learning problems. Although it is well known that a DS problem …

Submodular function minimization (SFM) and matroid intersection are fundamental discrete
optimization problems with applications in many fields. It is well known that both of these can …