Ashutosh Rai
I am an Assistant Professor at Department of Mathematics, IIT Delhi. Prior to joining IIT Delhi, I was briefly associated with Computer Science Department IIIT, Delhi as an Assistant Professor. Before that, I was a postdoctoral fellow at Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University in Prague and a postdoc at Department of Computing, Hong Kong Polytechnic University, with Prof. Yixin Cao and his group. I did my masters and PhD from Institute of Mathematical Sciences (IMSc), Chennai, where I was advised by Prof. Saket Saurabh and Prof. Venkatesh Raman.
My basic interest lies in Theoretical Computer Science. Much of my research till now has been about dealing with NP-complete problems in algorithmic ways, including fixed-paramater tractability and kernelization. I am also interested in connections between parameterized complexity and classical complexity and the hardness theory arising from that.
Contact:
Department of Mathematics
Room MZ-170, Department of Mathematics
Indian Institute of Technology Delhi
Hauz Khas, New Delhi, 110016
India
e-mail: (firstname) [dot] (lastname) [at] maths [dot] iitd [dot] ac [dot] in
Teaching:
- Analysis and Design of Algorithms, Monsoon 2023, IIT Delhi.
- Theory of Computation, Monsoon 2023, IIT Delhi.
- Parameterized Algorithms for NP-complete Problems, Spring 2023, IIT Delhi.
- Computing Laboratory, Spring 2023, IIT Delhi.
- Operating Systems, Monsoon 2022, IIT Delhi.
- Topics in Algorithms (Seminar Course), Monsoon 2022, IIT Delhi.
- Computing Laboratory, Spring 2022, IIT Delhi.
- Advanced Algorithms, Spring 2022, IIT Delhi, taught with Prof. Minati De.
- Analysis and Design of Algorithms, Monsoon 2021, IIT Delhi.
- Combinatorics, Monsoon 2021, IIT Delhi, taught with Prof. Minati De.
- Operating Systems, Spring 2021, IIT Delhi.
- Complexity Theory, Monsoon 2020, at IIIT, Delhi.
- Combinatorics and Graph Theory I, Spring 2019, at Charles University (assisted Prof. Andreas Emil Feldmann).
- Advanced Graph Algorithms, early 2014, at IMSc, Chennai (assisted Prof. Saket Saurabh).
Research:
In JournalsIn Conferences
- A Polynomial Kernel for Diamond-Free Editing
with Yixin Cao, R. B. Sandeep, and Junjie Ye
in Algorithmica, Volume 84(1), Pages 197-215 (2022). [link] [preprint]- Parameterized and exact algorithms for class domination coloring
with R. Krithika, Saket Saurabh, and Prafullkumar Tale
in Discrete Applied Mathematics, Volume 291, Pages 286-299 (2021). [link] [preprint]- Parameterized Algorithms for Max Colorable Induced Subgraph problem on Perfect Graphs
with Neeldhara Misra, Fahad Panolan, Venkatesh Raman, and Saket Saurabh
in Algorithmica, Volume 81(1), Pages 26-46 (2019). [link] [preprint]- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
with Geevarghese Philip and Saket Saurabh
in SIAM Journal on Discrete Mathematics (SIDMA), Volume 32(2), Pages 882-901 (2018). [link] [preprint]- On the Kernelization Complexity of String Problems
with Manu Basavaraju, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh
in Theoretical Computer Science (2018), Volume 730, Pages 21-31 (2018). [link] [preprint]- Bivariate complexity analysis of Almost Forest Deletion with Saket Saurabh
in Theoretical Computer Science, Volume 708, Pages 18-33 (2018). [link] [preprint]- Faster Parameterized Algorithms for Deletion to Split Graphs
with Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, and M. S. Ramanujan
in Algorithmica, Volume 71(4), Pages 989-1006 (2015). [link] [preprint]- Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs
with Stefan Kratsch, Marcin Pilipczuk, and Venkatesh Raman
in ACM Transactions on Computation Theory (TOCT), Volume 7(1), Pages 4:1-4:18 (2014). [link] [preprint]Theses
- Parameterized complexity of untangling knots
with Clement Legrand-Duchesne and Martin Tancer [pdf]
in EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2022.- Parameterized Complexity of Set-Restricted Disjoint Paths on Chordal Graphs
with Petr A. Golovach, Fahad Panolan, and Saket Saurabh [pdf]
in International Computer Scinece Symposium in Russia (CSR), 2022.- On Extended Formulations For Parameterized Steiner Trees
with Andreas Emil Feldmann [pdf]
in International Symposium on Parameterized and Exact Computation (IPEC), 2021.- Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
with Andreas Emil Feldmann and Davis Issac [pdf]
in International Symposium on Parameterized and Exact Computation (IPEC), 2020.- Quick Separation in Chordal and Split Graphs [pdf]
with Pranabendu Misra, Fahad Panolan, Saket Saurabh, and Roohani Sharma
in Mathematical Foundations of Computer Science (MFCS), 2020.- Parameterized Inapproximability of Independent Sets in H-Free Graphs [pdf]
with Pavel Dvořák, Andreas Emil Feldmann, and Paweł Rzążewski
in International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2020.- A Polynomial Kernel for Diamond-Free Editing [pdf]
with Yixin Cao, R. B. Sandeep, and Junjie Ye
in European Symposium on Algorithms (ESA), 2018.- Parameterized and Exact Algorithms for Class Domination Coloring [pdf]
with R. Krithika, Saket Saurabh, and Prafullkumar Tale
in International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2017.- Lossy Kernels for Graph Contraction Problems [pdf]
with R. Krithika, Pranabendu Misra, and Prafullkumar Tale
in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016.- Strong Graph Deletion: Bipartite Graphs [pdf]
with M. S. Ramanujan
in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016.- A Parameterized Algorithm for Mixed-Cut [pdf]
with M. S. Ramanujan and Saket Saurabh
in Latin American Theoretical Informatics Symposium (LATIN), 2016.- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel [pdf]
with Geevarghese Philip and Saket Saurabh
in Mathematical Foundations of Computer Science (MFCS), 2015.- Bivariate Complexity Analysis of Almost Forest Deletion [pdf]
with Saket Saurabh
in Annual International Computing and Combinatorics Conference (COCOON), 2015.- Kernel Lower Bounds on String Problems [pdf]
with Manu Basawaraju, Fahad Panolan, Saket Saurabh, and M. S. Ramanujan
in Annual International Computing and Combinatorics Conference (COCOON), 2014.- Polynomial Kernels for $\lambda$-extendible Properties Parameterized Above the Poljak-Turzík Bound [pdf]
with Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, and Saket Saurabh
in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2013.- Parameterized Algorithms for Max Colorable Induced Subgraph problem on Perfect Graphs[pdf]
with Neeldhara Misra, Fahad Panolan, Venkatesh Raman, and Saket Saurabh
in International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2013.- Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs [pdf]
with Stefan Kratsch, Marcin Pilipczuk, and Venkatesh Raman
in Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.- Faster Parameterized Algorithms for Deletion to Split Graphs [pdf]
with Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, and M. S. Ramanujan
in Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.- On the kernelization complexity of problems on graphs without long odd cycles [pdf]
with Fahad Panolan
in Annual International Computing and Combinatorics Conference (COCOON), 2012.
- Parameterized Algorithms for Graph Modification Problems [pdf]
PhD thesis
- Kernel Lower Bounds: A Survey [pdf]
Master's thesis