Publications
2024
Query Maintenance Under Batch Changes with Small-Depth Circuits
Datta, S., Khan, A., Mukherjee, A., Tschirbs, F., Vortmeier, N., & Zeume, T. (2024). Query Maintenance Under Batch Changes with Small-Depth Circuits. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 306. doi:10.4230/LIPIcs.MFCS.2024.46
Log Diameter Rounds MST Verification and Sensitivity in MPC
Coy, S., Czumaj, A., Mishra, G., & Mukherjee, A. (2024). Log Diameter Rounds MST Verification and Sensitivity in MPC. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 269-280). ACM. doi:10.1145/3626183.3659984
Streaming Graph Algorithms in the Massively Parallel Computation Model
Czumaj, A., Mishra, G., & Mukherjee, A. (2024). Streaming Graph Algorithms in the Massively Parallel Computation Model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (pp. 496-507). ACM. doi:10.1145/3662158.3662770
Shortest Disjoint Paths on a Grid
Mari, M., Mukherjee, A., & Sankowski, P. (2024). Shortest Disjoint Paths on a Grid. In Unknown Conference (pp. 346-365). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977912.14
2023
Approximating Edit Distance in the Fully Dynamic Model
Kociumaka, T., Mukherjee, A., & Saha, B. (2023). Approximating Edit Distance in the Fully Dynamic Model. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1628-1638). IEEE. doi:10.1109/focs57990.2023.00098
Dynamic Planar Embedding Is in DynFO
Datta, S., Khan, A., & Mukherjee, A. (2023). Dynamic Planar Embedding Is in DynFO. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 272. doi:10.4230/LIPIcs.MFCS.2023.39
2022
Dynamic Meta-Theorems for Distance and Matching
Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V. R., & Tewari, R. (2022). Dynamic Meta-Theorems for Distance and Matching. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 229. doi:10.4230/LIPIcs.ICALP.2022.118
Subquadratic dynamic path reporting in directed graphs against an adaptive adversary
Karczmarz, A., Mukherjee, A., & Sankowski, P. (2022). Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1643-1656). ACM. doi:10.1145/3519935.3520058
Frameworks for designing in-place graph algorithms
Chakraborty, S., Mukherjee, A., Raman, V., & Satti, S. R. (2022). Frameworks for designing in-place graph algorithms. Journal of Computer and System Sciences, 123, 1-19. doi:10.1016/j.jcss.2021.07.004
Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value
Karczmarz, A., Michalak, T., Mukherjee, A., Sankowski, P., & Wygocki, P. (2022). Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value. In Proceedings of Machine Learning Research Vol. 180 (pp. 980-989).
Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value
Karczmarz, A., Michalak, T., Mukherjee, A., Sankowski, P., & Wygocki, P. (2022). Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022 (pp. 969-979).
The Parameterized Complexity of the Survivable Network Design Problem
Feldmann, A. E., Mukherjee, A., & van Leeuwen, E. J. (2022). The Parameterized Complexity of the Survivable Network Design Problem. In Unknown Conference (pp. 37-56). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977066.4
2021
Reachability and Matching in Single Crossing Minor Free Graphs
Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V. R., & Tewari, R. (2021). Reachability and Matching in Single Crossing Minor Free Graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 213. doi:10.4230/LIPIcs.FSTTCS.2021.16
Decomposable Submodular Function Minimization via Maximum Flow
Axiotis, K., Karczmarz, A., Mukherjee, A., Sankowski, P., & Vladu, A. (2021). Decomposable Submodular Function Minimization via Maximum Flow. In Proceedings of Machine Learning Research Vol. 139 (pp. 446-456).
2020
Dynamic complexity of reachability: How many changes can we handle?
Datta, S., Kumar, P., Mukherjee, A., Tawari, A., Vortmeier, N., & Zeume, T. (2020). Dynamic complexity of reachability: How many changes can we handle?. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 168. doi:10.4230/LIPIcs.ICALP.2020.122
2019
A strategy for dynamic programs: Start over and muddle through
Datta, S., Mukherjee, A., Schwentick, T., Vortmeier, N., & Zeume, T. (2019). A strategy for dynamic programs: Start over and muddle through. Logical Methods in Computer Science, 15(2), 12:1-12:26. doi:10.23638/LMCS-15(2:12)2019
Space Efficient Algorithms for Breadth-Depth Search
Chakraborty, S., Mukherjee, A., & Satti, S. R. (2019). Space Efficient Algorithms for Breadth-Depth Search. In Unknown Conference (pp. 201-212). Springer International Publishing. doi:10.1007/978-3-030-25027-0_14
2018
Planar maximum matching: Towards a parallel algorithm
Datta, S., Kulkarni, R., Kumar, A., & Mukherjee, A. (2018). Planar maximum matching: Towards a parallel algorithm. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 123. doi:10.4230/LIPIcs.ISAAC.2018.21
Shortest k-disjoint paths via determinants
Datta, S., Iyer, S., Kulkarni, R., & Mukherjee, A. (2018). Shortest k-disjoint paths via determinants. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 122. doi:10.4230/LIPIcs.FSTTCS.2018.19
Reachability Is in DynFO
Datta, S., Kulkarni, R., Mukherjee, A., Schwentick, T., & Zeume, T. (2018). Reachability Is in DynFO. Journal of the ACM, 65(5), 1-24. doi:10.1145/3212685
A framework for in-place graph algorithms
Chakraborty, S., Mukherjee, A., Raman, V., & Satti, S. R. (2018). A framework for in-place graph algorithms. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 112. doi:10.4230/LIPIcs.ESA.2018.13
Reachability and distances under multiple changes
Datta, S., Mukherjee, A., Vortmeier, N., & Zeume, T. (2018). Reachability and distances under multiple changes. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 107. doi:10.4230/LIPIcs.ICALP.2018.120
2017
A strategy for dynamic programs: Start over and muddle through
Datta, S., Mukherjee, A., Schwentick, T., Vortmeier, N., & Zeume, T. (2017). A strategy for dynamic programs: Start over and muddle through. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 80. doi:10.4230/LIPIcs.ICALP.2017.98
2016
Space-efficient approximation scheme for maximum matching in sparse graphs
Datta, S., Kulkarni, R., & Mukherjee, A. (2016). Space-efficient approximation scheme for maximum matching in sparse graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 58. doi:10.4230/LIPIcs.MFCS.2016.28
2015
Reachability is in DynFO
Datta, S., Kulkarni, R., Mukherjee, A., Schwentick, T., & Zeume, T. (2015). Reachability is in DynFO. In Lecture Notes in Computer Science (pp. 159-170). Springer Berlin Heidelberg. doi:10.1007/978-3-662-47666-6_13