Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]) can guarantee a solution that is $(1+ϵ)$-approximation at best while the exact $\tilde O(n^{0.

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 ${\mathcal{M}}_1=(V,{\mathcal{I}}_1)$ and ${\mathcal{M}}_2=(V,{\mathcal{I}}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S\in {\mathcal{I}}_1\cap {\mathcal{I}}_2$ by making independence oracle queries of the form ''Is $S\in {\mathcal{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$. This problem is an important subroutine in Karger's celebrated randomized near-linear-time min-cut algorithm [STOC'96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs.

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). At the core of our technique is a novel simulation theorem. Alice gets a $p\times n$ matrix $x$ over ${\mathbb{F}}_2$ and Bob gets a vector $y\in {\mathbb{F}}_2^n$. Alice and Bob need to evaluate $f(x\cdot y)$ for a Boolean function $f$.