A Note on Isolating Cut Lemma for Submodular Function Minimization

It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the non-trivial minimizer of a symmetric submodular function and solving the hypergraph minimum cut problem. This note contains these observations.

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs

We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$, our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOC’20; GMW SOSA’21]. This improves the previous best work by Geissmann and Gianinazzi [SPAA’18] by $O(\log^3 n)$ factor, while matching the depth of their algorithm.

Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition

We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min{\lambda n^2, n^r/\lambda})$, where $p$ is the size, $n$ is the number of vertices, $r$ is the rank (size of the largest hyperedge), and $\lambda$ is the connectivity of the hypergraph. The $\hat O_r(\cdot)$ hides terms that are subpolynomial in the main parameter and terms that depend only on $r$. Our algorithm is faster than existing algorithms when the connectivity $\lambda$ is $\Omega(n^{(r-2)/2})$.

Distributed Weighted Min-Cut in Nearly-Optimal Time

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+\epsilon)$-approximation at best while the exact $\tilde O(n^{0.

Breaking the Quadratic Barrier for Matroid Intersection

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$?

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

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.

Simulation Theorems via Pseudo-random Properties

We generalize the deterministic simulation theorem of Raz-Mckenzie, to any gadget which satisfies a certain hitting property. We prove that Inner-product and gap-Hamming satisfy this property, and, as a corollary, we obtain deterministic simulation theorem for these gadgets, where the gadget's input-size is logarithmic in the input-size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Goos-Pitassi-Watson.

Lifting Theorems for Equality

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ \mathsf{Eq}_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ \mathsf{Eq}_n$ is $\Omega(deg(f) \cdot n)$. However, there is a surprising counter-example of a partial function $f$ on $p$ bits, such that any completion $f'$ of $f$ has $\deg(f') = \Omega(p)$, and yet $f \circ \mathsf{Eq}_n$ has communication complexity $O(n)$.

Simulation Beats Richness: New Data-Structure Lower Bounds

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$.

Lower Bounds for Elimination via Weak Regularity

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f : {0, 1}^{2n} \to {0, 1}$ be any boolean function. Alice and Bob get $k$ inputs $x_1, \cdots , x_k$ and $y_1, \cdots, y_k$ respectively, with $x_i, y_i \in {0, 1}^n$. They want to output a $k$-bit vector $v$, such that there exists one index $i$ for which $v_i \neq f(x_i, y_i)$.

Separation between Deterministic and Randomized Query Complexity

Saks and Wigderson [FOCS 1986] conjectured that $R_0(f)=\Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$. We show that for the pointer function $GPW_{r \times s}$ defined by Goos, Pitassi, and Watson [FOCS 2015], the following hold: $R_1(GPW_{r \times s})=\tilde\Theta(r + s)$ and $R_1(\overline{GPW_{r \times s}})=\tilde \Theta(r + \sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(GPW_{s^2 \times s})=O(D(GPW_{s^2 \times s})^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(GPW_{s \times s})=\tilde O(R_0(GPW_{s \times s})^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one sided error query complexity measures.

Tribes is Hard in Message-passing Model

We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels.

Towards Better Separation between Deterministic and Randomized Query Complexity

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by Saks and Wigderson that for any Boolean function $f$, $R_0(f)=\Omega({D(f)})^{0.753..}$. This also shows widest separation between $R_1(f)$ and $D(f)$ for any Boolean function. The function $F$ was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity.