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 …

Abstract Deep Neural Networks and Reinforcement Learning methods have empirically
shown great promise in tackling challenging combinatorial problems. In those methods a …

We study the complexity of determining the edge connectivity of a simple graph with cut
queries. We show that (i) there is a bounded-error randomized algorithm that computes …

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 (SFM) and matroid intersection are fundamental discrete
optimization problems with applications in many fields. It is well known that both of these can …

The matroid intersection problem is a fundamental problem that has been extensively
studied for half a century. In the classic version of this problem, we are given two matroids M …

We study an extension of the stochastic submodular minimization problem, namely, the
stochastic $ L^\natural $-convex minimization problem. We develop the first polynomial-time …

Let $ G=(V, w) $ be a weighted undirected graph with $ m $ edges. The cut dimension of $ G
$ is the dimension of the span of the characteristic vectors of the minimum cuts of $ G …

In this paper we describe a randomized algorithm which returns a maximal spanning forest
of an unknown {\em weighted} undirected graph making $ O (n) $$\mathsf {CUT} $ queries …

We consider the problem of finding a spanning forest in an unknown {\em weighted}
undirected graph when the access to the graph is via CUT queries, that is, one can query a …