Recent publications
Conference contribution
Fischer, O, Jiang, Y, Mukhopadhyay, S & Yingchareonthawornchai, S 2026, Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. in S Assadi & E Rotenberg (eds), 2026 SIAM Symposium on Simplicity in Algorithms (SOSA). Proceedings of the SIAM Symposium on Simplicity in Algorithms, Society for Industrial and Applied Mathematics Publications, pp. 413-420, 9th SIAM Symposium on Simplicity in Algorithms, Vancouver, Canada, 12/01/26. https://doi.org/10.1137/1.9781611978964.33
Chalermsook, P, Jiang, Y, Mukhopadhyay, S & Nanongkai, D 2026, Shortcuts and Transitive-Closure Spanners Approximation. in KG Larsen & B Saha (eds), Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 3536-3561, 37th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, Canada, 11/01/26. https://doi.org/10.1137/1.9781611978971.129
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
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
View all publications in research portal