Publications

21.  Streaming Graph Algorithms in the Massively Parallel Computation Model

with Artur Czumaj and Gopinath Mishra

  43rd ACM Symposium on Principles of Distributed Computing (PODC 2024) in Nantes, France 

20.  Log Diameter Rounds MST Verification and Sensitivity in MPC

with Sam Coy, Artur Czumaj, and Gopinath Mishra

36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2024) in Nantes, France

19.  Shortest Disjoint Paths on a Grid  [pdf]

with Mathieu Mari, Michał Pilipczuk, and Piotr Sankowski 

ACM-SIAM Symposium on Discrete Algorithms (SODA 2024) in Alexandria, VA, US

18.  Approximating Edit Distance in the Fully Dynamic Model  [arXiv][talk by Barna]

with Tomasz Kociumaka and Barna Saha

 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023) in Santa Cruz, CA, US 

17.  Dynamic Planar Embedding is in DynFO  [arXiv]  

with Samir Datta  and Asif Khan

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) in Bordeaux, France

16.  Modeling Online Paging in Multi-Core Systems  [arXiv] 

with Mathieu Mari, Runtian Ren,  and Piotr Sankowski

15.  Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary  [arXiv] [talk] [poster]

with Adam Karczmarz and Piotr Sankowski

54th ACM Symposium on Theory of Computing (STOC 2022) in Rome, Italy

14.  Dynamic Meta-theorems for Distance and Matching  [arXiv]  

with Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari

49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP-B 2022) in Paris, France

13.  Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf  [arXiv] [code] 

with  Adam Karczmarz, Tomasz Michalak, Piotr Sankowski, and  Piotr Wygocki

38th Conference on Uncertainty in Artificial Intelligence (UAI 2022) in Eindhoven, The Netherlands

12.  The Parameterized Complexity of the Survivable Network Design Problem  [arXiv] [talk by Andreas] 

with Andreas Emil Feldmann and Erik Jan van Leeuwen

Highlights of Algorithms (HALG 2022) in London, UK

SIAM Symposium on Simplicity in Algorithms (SOSA 2022) in Virginia, US (Virtual)

11.  Frameworks for Designing In-place Graph Algorithms  [arXiv]

with Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti 

Journal of Computer and System Sciences (JCSS), Volume 123, February 2022

26th Annual European Symposium on Algorithms (ESA 2018) in Helsinki, Finland 

10.  Reachability and Matching in Single Crossing Minor Free Graphs  [arXiv] [talk by Chetan] 

with Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari

41st IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

9.  Decomposable Submodular Function Minimization via Maximum Flow  [arXiv] [talk by Kyriakos] 

with Kyriakos Axiotis, Adam Karczmarz, Piotr Sankowski, and Adrian Vladu

38th International Conference on Machine Learning (ICML 2021)

8.  Dynamic Complexity of Reachability: How many changes can we handle?  [arXiv] [talk by Nils]

with Samir Datta, Pankaj Kumar, Anuj Tawari, Nils Vortmeier, and Thomas Zeume

47th International Colloquium on Automata, Languages, and Programming (ICALP-B 2020) in Saarbrücken, Germany

7.  Space-efficient Breadth-depth Search  [pdf]

with Sankardeep Chakraborty and Srinivasa Rao Satti

22nd Symposium on Fundamentals of Computation Theory  (FCT 2019) in Copenhagen, Denmark 

6.  A Strategy for Dynamic Programs: Start over and Muddle through  [arXiv]

with Samir Datta, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume

(Invited to the Special Issue) Logical Methods in Computer Science (LMCS), Volume 15 Issue 2, May 2019 

44th International Colloquium on Automata, Languages, and Programming (ICALP-B 2017) in Warsaw, Poland 

5.  Planar Maximum Matching: Towards a Parallel Algorithm  [pdf]

with Samir Datta, Raghav Kulkarni, and Ashish Kumar

29th International Symposium on Algorithms and Computation (ISAAC 2018) in Jiaoxi, Taiwan

4.  Shortest k-Disjoint Paths via Determinants  [arXiv]

with Samir Datta, Siddharth Iyer, and Raghav Kulkarni 

38th IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) in Ahmedabad, India

3.  Reachability is in DynFO  [arXiv]

with Samir Datta, Raghav Kulkarni, Thomas Schwentick, and Thomas Zeume

Journal of the ACM (J. ACM), Volume 65 Issue 5, September 2018

42nd International Colloquium on Automata, Languages, and Programming (ICALP-B 2015) in Kyoto, Japan 

2.  Reachability and Distances under Multiple Changes  [arXiv]

with Samir Datta, Nils Vortmeier, and Thomas Zeume

45th International Colloquium on Automata, Languages, and Programming (ICALP-B 2018) in Prague, Czech Republic 

1.  Space-efficient Approximation Scheme for Maximum Matching in Sparse Graphs  [paper] [talk @IITGN]

with Samir Datta and Raghav Kulkarni

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) in Krakow, Poland