Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
1
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.
Andrés López-Martínez
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Video
arXiv
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.
Michal Dory
,
Yuval Efron
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Video
arXiv
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$?
Joakim Blikstad
,
Jan van den Brand
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Video
arXiv
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$.
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Slides
Video
arXiv
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)$.
Bruno Loff
,
Sagnik Mukhopadhyay
PDF
Cite
Slides
DOI
ECCC
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).
Arkadev Chattopadhyay
,
Michal Koucký
,
Bruno Loff
,
Sagnik Mukhopadhyay
PDF
Cite
Slides
Video
DOI
ECCC
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.
Arkadev Chattopadhyay
,
Michal Koucký
,
Bruno Loff
,
Sagnik Mukhopadhyay
PDF
Cite
Video
DOI
DOI
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}$.
Sagnik Mukhopadhyay
,
Swagato Sanyal
PDF
Cite
Slides
DOI
arXiv
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.
Arkadev Chattopadhyay
,
Sagnik Mukhopadhyay
PDF
Cite
Slides
DOI
arXiv
Cite
×