News: papers accepted to SODA'24 and ITCS'24 (more...)
I am an Assistant Professor in Computer Science at the Chennai Mathematical Institute (CMI), India.
In the recent past, I was a postdoctoral fellow in the Algorithms and Complexity department at the Max Planck Institute for Informatics, Saarbrucken, Germany. Earlier, I was a researcher in the Algorithms group at the Department of Informatics, University of Bergen, Norway.
I obtained my PhD in Computer Science, advised by Prof. Saket Saurabh, from the Institute of Mathematical Sciences (IMSc), India and my masters and undergraduate degree from CMI in Mathematics and Computer Science.
Grants, Awards …
- Research Project grant Fujitsu 2023
- jointly with Priyavrat Deshpande and Nithin Varma
- Google India Research Award 2022
- SERB (India) Startup Research Grant (SRG) 2022
Research Interests
Algorithms and their applications.
Research Areas: Graph Theory, Parameterized Complexity, Approximation Algorithms, Matroids, Algebraic methods, Derandomization, Algorithmic Game Theory, Streaming algorithms, Dynamic and Fault-tolerant graphs, Optimization and recently AI/ML and Deep Learning.
Publications
(Also available at DBLP and Google Scholar.)
- Meta-theorems for Parameterized Streaming Algorithms
- with Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh and Meirav Zehavi
- SODA 2024
- Kernelization of Counting Problems
- with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
- ITCS 2024
- Parameterized Approximation Algorithms for Weighted Vertex Cover
- with Soumen Mandal, Ashutosh Rai and Saket Saurabh
- LATIN 2024
- An ETH-Tight Algorithm for Bidirected Steiner Connectivity.
- with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- WADS 2023
- with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands
- Jørgen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh
- ESA 2023
- A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
- with Daniel Marx, Daniel Neuen and Prafullkumar Tale
- SODA 2022
- Improving EFX Guarantees through Rainbow Cycle Number
- with Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn and Ruta Mehta
- EC 2021
- Strong Connectivity Augmentation is FPT
- with Kristine Vitting Klinkby and Saket Saurabh
- SODA 2021
- FPT Approximation for FPT Problems
- with Daniel Lokshtanov, MS Ramanujan, Saket Saurabh and Meirav Zehavi
- SODA 2021
- An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
- with Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh and Meirav Zehavi
- STOC 2020.
- Fault Tolerant Subgraphs with Applications in Kernelization
- with William Lochet, Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi
- ITCS 2020.
- 2-Approximating Feedback Vertex Set in Tournaments
- with Daniel Lokshtanov, Joydeep Mukherjee, Geevarghese Philip, Fahad Panolan, Saket Saurabh
- SODA 2020.
- On the Complexity of Recovering Incidence Matrices
- with Ramanujan M. S., Petr Golovach and Fedor Fomin
- ESA 2020.
- A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion
- with Daniel Lokshtanov, Fahad Panolan, Geevarghese Philip and Saket Saurabh
- ICALP 2020.
- Quick Separation in Chordal and Split Graphs
- with Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani Sharma
- MFCS 2020.
- Parameterized Complexity of Directed Spanner Problems
- with Fedor Fomin, Petr Golovach, William Lochet, Saket Saurabh and Roohani Sharma
- IPEC 2020
- Popular Matching in the Roommates Setting is NP-hard
- with Sushmita Gupta, Saket Saurabh, and Meirav Zehavi
- SODA 2019
- Interval Vertex Deletion Admits a Polynomial Kernel
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- SODA 2019
- An Erdős-Pósa Theorem on Neighborhoods and Domination Number
- with Jayakrishnan Madathil and Saket Saurabh
- COCOON 2019
- Parameterized Algorithms for Survivable Network Design with Uniform Demands
- with Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Ramanujan M. S., Saket Saurabh and Meirav Zehavi
- SODA 2018
- Erdos-Posa Property of Obstructions to Interval Graphs
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- STACS 2018
- Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
- with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- ITCS 2018
- Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- APPROX 2018
- Journal: ACM Transactions on Algorithms, 2020.
- Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
- with Roohani Sharma, Saket Saurabh and Meirav Zehavi
- FSTTCS 2018
- Exploring the Kernelization Borders for Hitting Cycles
- with Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh and Saket Saurabh
- IPEC 2018
- Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
- with Pallavi Jain and Lawqueen Kanesh
- CSR 2018
- Journal: Theory of Computing Systems, 2020.
- An FPT Algorithm for Contraction to Cactus.
- with R. Krithika and Prafullkumar Tale.
- COCOON 2018
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
- SODA 2017
- Journal: ACM Transactions on Algorithms, 2019.
- Fast Exact Algorithms for Survivable Network Design with Uniform Requirements.
- with Akanksha Agarwal, Fahad Panolan and Saket Saurabh.
- WADS 2017
- Derandomization of Transversal Matroids and Gammoids in Moderately Exponential Time.
- with Fahad Panolan, M.S. Ramanujan and Saket Saurabh.
- COCOON 2017
- Journal: Theoretical Computer Science, 2020.
- Hitting Selected (Odd) Cycles.
- with Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.
- Journal: In SIAM Journal of Discrete Mathematics 31(3):1581-1615 (2017).
- Lossy Kernels for Graph Contraction Problems
- with R Krithika, Ashutosh Rai and Prafullkumar Tale.
- FSTTCS 2016
- Deterministic Truncation of Linear Matroids.
- with Daniel Lokshtanov, Fahad Panolan and Saket Saurabh.
- ICALP 2015
- Journal: ACM Transactions on Algorithms, 2018.
- Reducing Rank of the Adjacency Matrix by Graph Modification.
- with S. M. Meesum and Saket Saurabh
- COCOON 2015
- Journal: Theoretical Computer Science 654:70-79 (2016).
- Finding Even Subgraphs Even Faster.
- with Prachi Goyal, Fahad Panolan, Geevarghese Philip and Saket Saurabh.
- FSTTCS 2015
- Journal: Journal of Computer and System Sciences, 2018.
- Parameterized Algorithms to Preserve Connectivity.
- with Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan and Saket Saurabh.
- ICALP 2014
- Faster Graph Bipartization
- with Sudeshna Kolay, M. S. Ramanujan and Saket Saurabh.
- MFCS 2014
- Journal: Journal of Computer and System Sciences, 2020.
- Faster Exact Algorithms for Some Terminal Set Problems.
- with Rajesh H. Chitnis, Fedor V. Fomin, Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.
- IPEC 2013
- Journal: Journal of Computing and System Sciences 88:195-207 (2017).
- Faster Parameterized Algorithms for Deletion to Split Graphs
- with Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Fahad Panolan, Ashutosh Rai and M. S. Ramanujan.
- SWAT 2012
- Journal: Algorithmica 71(4): 989-1006 (2015).
- Parameterized Algorithms for Even Cycle Transversal
- with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.
- WG 2012
- A polynomial kernel for Feedback Arc Set on bipartite tournaments.
- with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.
- ISAAC 2011
- Journal: Theory of Computing Systems 53(4):609-620 (2013).
Manuscripts
- Deterministic Representation of Gammoids in Quasipolynomial time with Applications
- with Rohit Gurjar, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- A Brief Note on Single Source Fault Tolerant Reachability
- with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
- On Fault Tolerant Feedback Vertex Set
Thesis
- PhD Thesis: Parameterized Algorithms for Network Design.
Teaching
- [Approximation Algorithms]
- Spring 2024, Chennai Mathematical Institute
- Introduction to Generative Models
- Spring 2024, Chennai Mathematical Institute
- with Dinesh Kirthivasan (Kantar)
- Advanced Machine Learning
- Autumn 2023, Chennai Mathematical Institute
- Data Mining and Machine Learning
- Spring 2023, Chennai Mathematical Institute
- with Madhavan Mukund
- Advanced Machine Learning
- Autumn 2022, Chennai Mathematical Institute
- Approximation Algorithms
- Spring 2022, Chennai Mathematical Institute
- with Nithin Varma
- Advanced Machine Learning
- Autumn 2021, Chennai Mathematical Institute
- with Madhavan Mukund
- Theoretical Foundations of Machine Learning
- Autumn 2021, Chennai Mathematical Institute
- with K V Subrahmanyam
- Parameterized Algorithms
- Summer 2020, Max-Planck Institute for Informatics
- with Daniel Marx and Philip Wellnitz
- Distributed and Sequential Graph Algorithms
- Summer 2019, Max-Planck Institute for Informatics
- with Saeed Amiri and Cosmina Croitoru
Contact
pranabendu.m [__A_T___] gmail.com
pranabendu@cmi.ac.in
Postal address
Chennai Mathematical Institute
H1, SIPCOT IT Park, Siruseri
Kelambakkam, Chennai 603103
India