Publications

Caveat: In theoretical computer science (TCS), the most important publication venues are conferences, amongst which STOC, FOCS, SODA, CCC, and ICALP are widely recognised as the most prestigious worldwide. For journals, SICOMP and JACM are the most prestigious in the field.
The Power of the Score Sequence of a Tournament
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra, Sagnik Mukhopadhyay
ESA 2026
Best Paper Award (Track S)
arXiv (soon)DBLP
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
SOSA 2026
arXivDBLP
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
SODA 2026
arXivDBLP
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
STOC 2025
arXivDBLP
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
CCC 2024
arXivDBLP
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang, Sagnik Mukhopadhyay
STOC 2023
arXivDBLP
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Danupon Nanongkai, Ta-Wei Tu, Sagnik Mukhopadhyay
STOC 2023
arXivDBLP
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
FOCS 2022
arXivDBLP
Cut Query Algorithms with Star Contraction
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
FOCS 2022
arXivDBLP
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
IPCO 2022
arXivDBLP
A Note on Isolating Cut Lemma for Submodular Function Minimization
Sagnik Mukhopadhyay, Danupon Nanongkai
Preprint (2021)
arXivDBLP
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
SPAA 2021
arXivDBLP
Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
STOC 2021
arXivDBLP
Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
STOC 2021
arXivDBLP
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
STOC 2020
arXivDBLP
Simulation Theorems via Pseudo-random Properties
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Computational Complexity (28:4) 2019
arXivECCCDBLP
Lifting Theorems for Equality
Bruno Loff, Sagnik Mukhopadhyay
STACS 2019
ECCCDBLP
Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
STOC 2018
ECCCDBLP
Lower Bounds for Elimination via Weak Regularity
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
STACS 2017
ECCCDBLP
Separation between Deterministic and Randomized Query Complexity
Sagnik Mukhopadhyay, Swagato Sanyal, Jaikumar Radhakrishnan
SICOMP (47:4)
DOIDBLP
Tribes is Hard in Message-passing Model
Arkadev Chattopadhyay, Sagnik Mukhopadhyay
STACS 2015
arXivECCCDBLP
Towards Better Separation between Deterministic and Randomized Query Complexity
Sagnik Mukhopadhyay, Swagato Sanyal
FSTTCS 2015
arXivECCCDBLP