Dr Sagnik Mukhopadhyay
Department of Computer Science
Lecturer in Algorithms
Member of the Foundations of Computation research group
Full contact details
Department of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
- Profile
-
Dr. Sagnik Mukhopadhyay completed his Ph.D. from the Tata Institute of Fundamental Research, India in 2017. After finishing his Ph.D., he has spent 4 years at Royal Institute of Technology (KTH), Sweden, 6 months at Charles University, Czech Republic, and 6 months at Basic Algorithm Research Copenhagen (BARC) at the University of Copenhagen, Denmark as a post-doctoral researcher. From January 2022, Dr. Mukhopadhyay is a Lecturer in Algorithms at the Department of Computer Science.
- Research interests
-
Dr. Sagnik Mukhopadhyay's primary research areas are complexity theory (mainly communication complexity) and graph algorithms. In particular, his research focuses on investigating network problems through the lens of distributed systems, such as query, streaming, two-party communication, and distributed computational models. He designs efficient algorithms and/or proves the hardness of designing such algorithms for network problems in distributed computation. This area of research falls under the overarching umbrella of theoretical computer science.
- Publications
-
Show: Featured publications All publications
Featured publications
This person does not have any publications available.
All publications
Journal articles
- Simulation Theorems via Pseudo-random Properties. Computational Complexity, 28(4), 617-659.
- Separation between deterministic and randomized query complexity. SIAM Journal on Computing, 47(4), 1644-1666.
Chapters
- Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition, Integer Programming and Combinatorial Optimization (pp. 70-83).
Conference proceedings papers
- Finding a Small Vertex Cut on Distributed Networks. Proceedings of the 55th Annual ACM Symposium on Theory of Computing
- Fast Algorithms via Dynamic-Oracle Matroids. Proceedings of the 55th Annual ACM Symposium on Theory of Computing
- Nearly Optimal Communication and Query Complexity of Bipartite Matching. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 31 October 2022 - 3 November 2022.
- Cut Query Algorithms with Star Contraction. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 31 October 2022 - 3 November 2022.
- Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
- Distributed weighted min-cut in nearly-optimal time. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
- Breaking the quadratic barrier for matroid intersection. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
- Weighted min-cut: sequential, cut-query, and streaming algorithms. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
- Lifting theorems for equality. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 126
- Simulation beats richness: new data-structure lower bounds. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
- Lower bounds for elimination via weak regularity. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 66
- Towards better separation between deterministic and randomized query complexity. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 45 (pp 206-220)
- Tribes is hard in the message passing model. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 30 (pp 224-237)
- Balanced bipartitioning of a multi-weighted hypergraph for heterogeneous FPGAS. Proceedings of the 2011 7th Southern Conference on Programmable Logic, SPL 2011 (pp 91-96)
Preprints
- Finding a Small Vertex Cut on Distributed Networks, arXiv.
- Fast Algorithms via Dynamic-Oracle Matroids, arXiv.
- Nearly Optimal Communication and Query Complexity of Bipartite Matching, arXiv.
- Cut query algorithms with star contraction, arXiv.
- A Note on Isolating Cut Lemma for Submodular Function Minimization, arXiv.
- Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs, arXiv.
- Breaking the Quadratic Barrier for Matroid Intersection, arXiv.
- Faster connectivity in low-rank hypergraphs via expander decomposition, arXiv.
- Distributed Weighted Min-Cut in Nearly-Optimal Time, arXiv.
- Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms, arXiv.
- Simulation Theorems via Pseudorandom Properties, arXiv.
- Tribes Is Hard in the Message Passing Model, arXiv.
- Simulation Theorems via Pseudo-random Properties. Computational Complexity, 28(4), 617-659.
- Grants
-
Research Grants
- GraphCom: Communication Complexity of Graph Algorithms, UKRI, 12/2023 - 11/2026, £352,457, as PI