I am an associate professor in the School of Computer Science at the University of Birmingham. I am primarily associated with the Theory of Computation group. My research interest is in algorithms and complexity.

In my previous avatar, I was a lecturer (Assistant professor in North American equivalence) in the Department of Computer Science at the University of Sheffield, a post-doctoral researcher at the Department of Computer Science in the University of Copenhagen in 2021, at KTH Royal Institute of Technology during 2019-2021, a post-doctoral fellow at IUUK, Charles University in 2018, in the APC group at KTH Royal Institute of Technology during 2017-2018, and a graduate student in theoretical computer science at TIFR Mumbai until August 2017, working under the guidance of Dr. Arkadev Chattopadhyay.

I am a recipient of the UKRI New Investigator Award. During my PhD, I was a recipient of TCS PhD Fellowship and my PhD research work was supported by this fellowship.

Publications

Caveat: In theoretical computer science (TCS), the most important publication venues are conferences, amongst which STOC and FOCS are widely recognised as the most prestigious conferences worldwide. For journals, SICOMP and JACM are the most prestigious journals in the field.

1. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay In CCC 2024.
2. Finding a Small Vertex Cut on Distributed Networks. Yonggang Jiang, Sagnik Mukhopadhyay In STOC 2023.
3. Fast Algorithms via Dynamic-Oracle Matroids. Joakim Blikstad, Danupon Nanongkai, Ta-Wei Tu, Sagnik Mukhopadhyay In STOC 2023.
4. Nearly Optimal Communication and Query Complexity of Bipartite Matching. Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai In FOCS 2022.
5. Cut Query Algorithms with Star Contraction. Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai In FOCS 2022.
6. Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition. SCalvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai In IPCO 2022.
7. A Note on Isolating Cut Lemma for Submodular Function Minimization.. Sagnik Mukhopadhyay, Danupon Nanongkai (2021).
8. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai In SPAA 2021.
9. Distributed Weighted Min-Cut in Nearly-Optimal Time.. Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai In STOC 2021.
10. Breaking the Quadratic Barrier for Matroid Intersection. Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai In STOC 2021.
11. Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms. Sagnik Mukhopadhyay, Danupon Nanongkai In STOC 2020.
12. Simulation Theorems via Pseudo-random Properties. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay In Computational Complexity (28:4) 2019.
13. Lifting Theorems for Equality. Bruno Loff, Sagnik Mukhopadhyay In STACS 2019.
14. Simulation Beats Richness: New Data-Structure Lower Bounds. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay In STOC 2018.
15. Lower Bounds for Elimination via Weak Regularity. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay In STACS 2017.
16. Separation between Deterministic and Randomized Query Complexity. Sagnik Mukhopadhyay, Swagato Sanyal, Jaikumar Radhakrishnan In SICOMP (47:4).
17. Tribes is Hard in Message-passing Model. Arkadev Chattopadhyay, Sagnik Mukhopadhyay In STACS 2015.
18. Towards Better Separation between Deterministic and Randomized Query Complexity. Sagnik Mukhopadhyay, Swagato Sanyal In FSTTCS 2015.