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 | 55 | 2020 |
Simulation theorems via pseudo-random properties A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay computational complexity 28, 617-659, 2019 | 42 | 2019 |
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 | 27 | 2018 |
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 | 22 | 2021 |
Lifting theorems for equality B Loff, S Mukhopadhyay Leibniz International Proceedings in Informatics, LIPIcs 126, 50, 2019 | 22 | 2019 |
Towards better separation between deterministic and randomized query complexity S Mukhopadhyay, S Sanyal arXiv preprint arXiv:1506.06399, 2015 | 13 | 2015 |
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 | 12 | 2021 |
Tribes is hard in the message passing model A Chattopadhyay, S Mukhopadhyay arXiv preprint arXiv:1602.06079, 2016 | 12 | 2016 |
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 | 11 | 2022 |
A note on isolating cut lemma for submodular function minimization S Mukhopadhyay, D Nanongkai arXiv preprint arXiv:2103.15724, 2021 | 10 | 2021 |
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 | 9 | 2022 |
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 |
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 | 8 | 2023 |
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 | 6 | 2017 |
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 |
Faster connectivity in low-rank hypergraphs via expander decomposition C Beideman, K Chandrasekaran, S Mukhopadhyay, D Nanongkai International Conference on Integer Programming and Combinatorial …, 2022 | 4 | 2022 |
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 | 4 | 2021 |
Lifting Theorems for Equality. S Mukhopadhyay, B Loff STACS 2019, 36th International Symposium on Theoretical Aspects of Computer …, 2019 | 4 | 2019 |
Separation between deterministic and randomized query complexity S Mukhopadhyay, J Radhakrishnan, S Sanyal SIAM Journal on Computing 47 (4), 1644-1666, 2018 | 3 | 2018 |
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 | 2 | 2024 |