| Weighted min-cut: sequential, cut-query, and streaming algorithms S Mukhopadhyay, D Nanongkai Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020 | 79 | 2020 |
| Simulation theorems via pseudo-random properties A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay computational complexity 28 (4), 617-659, 2019 | 51 | 2019 |
| Distributed weighted min-cut in nearly-optimal time M Dory, Y Efron, S Mukhopadhyay, D Nanongkai Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 32 | 2021 |
| Cut query algorithms with star contraction S Apers, Y Efron, P Gawrychowski, T Lee, S Mukhopadhyay, ... 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 29 | 2022 |
| Simulation beats richness: new data-structure lower bounds A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 28 | 2018 |
| Nearly optimal communication and query complexity of bipartite matching J Blikstad, J Van Den Brand, Y Efron, S Mukhopadhyay, D Nanongkai 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 26 | 2022 |
| Lifting theorems for equality B Loff, S Mukhopadhyay Leibniz International Proceedings in Informatics, LIPIcs 126, 50, 2019 | 25 | 2019 |
| A note on isolating cut lemma for submodular function minimization S Mukhopadhyay, D Nanongkai arXiv preprint arXiv:2103.15724, 2021 | 18 | 2021 |
| Towards better separation between deterministic and randomized query complexity S Mukhopadhyay, S Sanyal arXiv preprint arXiv:1506.06399, 2015 | 18 | 2015 |
| Fast algorithms via dynamic-oracle matroids J Blikstad, S Mukhopadhyay, D Nanongkai, TW Tu Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1229-1242, 2023 | 16 | 2023 |
| Breaking the quadratic barrier for matroid intersection J Blikstad, J Van Den Brand, S Mukhopadhyay, D Nanongkai Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 14 | 2021 |
| Tribes is hard in the message passing model A Chattopadhyay, S Mukhopadhyay arXiv preprint arXiv:1602.06079, 2016 | 13 | 2016 |
| Composition and simulation theorems via pseudo-random properties A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay Electronic Colloquium on Computational Complexity (ECCC) 24, 14, 2017 | 9 | 2017 |
| Work-optimal parallel minimum cuts for non-sparse graphs A López-Martínez, S Mukhopadhyay, D Nanongkai Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and …, 2021 | 8 | 2021 |
| Lower bounds for elimination via weak regularity A Chattopadhyay, P Dvorák, M Koucký, B Loff, S Mukhopadhyay LIPIcs-Leibniz International Proceedings in Informatics 66, 2017 | 8 | 2017 |
| Finding a small vertex cut on distributed networks Y Jiang, S Mukhopadhyay Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1791-1801, 2023 | 6 | 2023 |
| Functions of bounded kth variation and absolutely kth continuous functions SK Mukhopadhyay, SN Mukhopadhyay Bulletin of the Australian Mathematical Society 46 (1), 91-106, 1992 | 6 | 1992 |
| Global vs. st Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations J Blikstad, Y Jiang, S Mukhopadhyay, S Yingchareonthawornchai Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2305-2316, 2025 | 5 | 2025 |
| Polynomial pass semi-streaming lower bounds for k-cores and degeneracy S Assadi, P Ghosh, B Loff, P Mittal, S Mukhopadhyay arXiv preprint arXiv:2405.14835, 2024 | 5 | 2024 |
| Directed and undirected vertex connectivity problems are equivalent for dense graphs O Fischer, Y Jiang, S Mukhopadhyay, S Yingchareonthawornchai 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), 413-420, 2026 | 4 | 2026 |
Danupon NanongkaiDirector, Max Planck Institute for InformaticsVerified email at mpi-inf.mpg.de
