Recent publications
Conference contribution
Blikstad, J, Jiang, Y, Mukhopadhyay, S & Yingchareonthawornchai, S 2025, Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations. in M Koucky & N Bansal (eds), STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 2305-2316, 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, 23/06/25. https://doi.org/10.1145/3717823.3718316
Assadi, S, Ghosh, P, Loff, B, Mittal, P & Mukhopadhyay, S 2024, Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. in 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 300, Schloss Dagstuhl, pp. 7:1-7:16, 39th Computational Complexity Conference, Ann Arbor, Michigan, United States, 22/07/24. https://doi.org/10.4230/LIPIcs.CCC.2024.7
Blikstad, J, Mukhopadhyay, S, Nanongkai, D & Tu, T-W 2023, Fast Algorithms via Dynamic-Oracle Matroids. in STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC: ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), pp. 1229-1242, 55th Annual ACM Symposium on Theory of Computing
, Orlando, Florida, United States, 20/06/23. https://doi.org/10.1145/3564246.358521
Jiang, Y & Mukhopadhyay, S 2023, Finding a Small Vertex Cut on Distributed Networks. in B Saha & RA Servedio (eds), STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery , pp. 1791-1801, 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, United States, 20/06/23. https://doi.org/10.1145/3564246.3585201
Apers, S, Efron, Y, Gawrychowski, P, Lee, T, Mukhopadhyay, S & Nanongkai, D 2022, Cut Query Algorithms with Star Contraction. in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 507-518, 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, United States, 31/10/22. https://doi.org/10.1109/FOCS54457.2022.00055
Beideman, C, Chandrasekaran, K, Mukhopadhyay, S & Nanongkai, D 2022, Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition. in K Aardal & L Sanità (eds), Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13265, Springer, pp. 70-83, 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, Eindhoven, Netherlands, 27/06/22. https://doi.org/10.1007/978-3-031-06901-7_6
Blikstad, J, Van Den Brand, J, Efron, Y, Mukhopadhyay, S & Nanongkai, D 2022, Nearly Optimal Communication and Query Complexity of Bipartite Matching. in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Annual IEEE Symposium on Foundations of Computer Science, IEEE. https://doi.org/10.1109/FOCS54457.2022.00113
Blikstad, J, Van Den Brand, J, Mukhopadhyay, S & Nanongkai, D 2021, Breaking the quadratic barrier for matroid intersection. in S Khuller & VV Williams (eds), STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery , pp. 421-432, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 21/06/21. https://doi.org/10.1145/3406325.3451092
Dory, M, Efron, Y, Mukhopadhyay, S & Nanongkai, D 2021, Distributed weighted min-cut in nearly-optimal time. in S Khuller & VV Williams (eds), STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery , pp. 1144-1153, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 21/06/21. https://doi.org/10.1145/3406325.3451020
Preprint
Jiang, Y, Mukhopadhyay, S & Yingchareonthawornchai, S 2025 'Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs' arXiv. https://doi.org/10.48550/arXiv.2508.20305
Chalermsook, P, Jiang, Y, Mukhopadhyay, S & Nanongkai, D 2025 'Shortcuts and Transitive-Closure Spanners Approximation' arXiv. https://doi.org/10.48550/arXiv.2502.08032
Jiang, Y & Mukhopadhyay, S 2023 'Finding a Small Vertex Cut on Distributed Networks' arXiv. https://doi.org/10.48550/arXiv.2302.11651
Apers, S, Efron, Y, Gawrychowski, P, Lee, T, Mukhopadhyay, S & Nanongkai, D 2022 'Cut query algorithms with star contraction' arXiv. https://doi.org/10.48550/arXiv.2201.05674
Mukhopadhyay, S & Nanongkai, D 2021 'A note on isolating cut lemma for submodular function minimization' arXiv. https://doi.org/10.48550/arXiv.2103.15724
López-Martínez, A, Mukhopadhyay, S & Nanongkai, D 2021 'Work-optimal parallel minimum cuts for non-sparse graphs' arXiv. https://doi.org/10.48550/arXiv.2102.06565
View all publications in research portal