SM
Sagnik Mukhopadhyay
cs.DScs.CCcs.DCcs.DMquant-ph
On Valency
published · living versionsW_hggp7tm4·v1 · currentpublished
A Simple Subquadratic Cut Query Protocol for Directed Reachability
with Henry Fleischmann, Swagato Sanyal
1 version
Preprints & journals
19 papers in the corpus · 2015–2026Bipartite Matching with Few Rounds of Demand Queries2610.18777v1 · Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah2026 · 0 citationsarXiv
The Power of the Score Sequence of a Tournament2607.15260v2 · Prantar Ghosh, Sahil Kuchlous, Shravan Mehra et al.2026 · 0 citationsarXiv
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs2508.20305v2 · Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay et al.2025 · 0 citationsarXiv
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations2503.20366v1 · Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay et al.2025 · 0 citationsarXiv
Shortcuts and Transitive-Closure Spanners Approximation2502.08032v3 · Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay et al.2025 · 0 citationsarXiv
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy2405.14835v1 · Sepehr Assadi, Prantar Ghosh, Bruno Loff et al.2024 · 3 citationsarXiv
Finding a Small Vertex Cut on Distributed Networks2302.11651v1 · Yonggang Jiang, Sagnik Mukhopadhyay2023 · 4 citationsarXiv
Fast Algorithms via Dynamic-Oracle Matroids2302.09796v2 · Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai et al.2023 · 7 citationsarXiv
Nearly Optimal Communication and Query Complexity of Bipartite Matching2208.02526v1 · Joakim Blikstad, Jan van den Brand, Yuval Efron et al.2022 · 9 citationsarXiv
Cut query algorithms with star contraction2201.05674v1 · Simon Apers, Yuval Efron, PawełGawrychowski et al.2022 · 6 citationsarXiv
A Note on Isolating Cut Lemma for Submodular Function Minimization2103.15724v1 · Sagnik Mukhopadhyay, Danupon Nanongkai2021 · 8 citationsarXiv
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs2102.06565v2 · Andr'es L'opez-Mart'inez, Sagnik Mukhopadhyay, Danupon Nanongkai2021 · 6 citationsarXiv
Breaking the Quadratic Barrier for Matroid Intersection2102.05548v2 · Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay et al.2021 · 6 citationsarXiv
Faster connectivity in low-rank hypergraphs via expander decomposition2011.08097v4 · Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay et al.2020 · 2 citationsarXiv
Distributed Weighted Min-Cut in Nearly-Optimal Time2004.09129v2 · Michal Dory, Yuval Efron, Sagnik Mukhopadhyay et al.2020 · 22 citationsarXiv
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms1911.01651v5 · Sagnik Mukhopadhyay, Danupon Nanongkai2019 · 35 citationsarXiv
Simulation Theorems via Pseudorandom Properties1704.06807v1 · Arkadev Chattopadhyay, Michal Kouck'y, Bruno Loff et al.2017 · 20 citationsarXiv
Tribes Is Hard in the Message Passing Model1602.06079v1 · Arkadev Chattopadhyay, Sagnik Mukhopadhyay2016 · 2 citationsarXiv
Towards Better Separation between Deterministic and Randomized Query Complexity1506.06399v2 · Sagnik Mukhopadhyay, Swagato Sanyal2015 · 4 citationsarXiv
Career total: 27 works. 19 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.