Publications

22.  Query Maintenance under Batch Changes with Small-depth Circuits  [arXiv]  

   with Samir Datta, Asif Khan, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume

    49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) in Bratislava, Slovakia 

21.  Streaming Graph Algorithms in the Massively Parallel Computation Model  [pdf]

   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  [arXiv]  

  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