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 edge connectivity with $O(n)$ cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with $\tilde O(\sqrt{n})$ cut queries.

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models.

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 ${\cal M}_1 = (V, {\cal I}_1)$ and ${\cal M}_2 = (V, {\cal I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S \in {\cal I}_1 \cap {\cal I}_2$ by making independence oracle queries of the form ‘‘Is $S \in {\cal I}_1$?

Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$.

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95).