Ashutosh Rai


photo

I am a postdoctoral fellow at Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University in Prague. Before this, I was working as 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.

You can find my CV here and my dblp page here. I also maintain a version of this page here.

I assisted Prof. Saket Saurabh for the Advanced Graph Algorithms course taught in early 2014, for which the lecture notes prepared by the students can be found here.


Contact:
 

Department of Applied Mathematics
Faculty of Mathematics and Physics, Charles University in Prague
Malostranské nám. 2/25, 118 00 Praha 1
Czech Republic

Room 324, 3rd floor, Malá Strana
e-mail: (firstname) [at] kam [dot] mff [dot] cuni [dot] cz

Publications:

  In Journals
  • 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]

  • Parameterized Algorithms for Max Colorable Induced Subgraph problem on Perfect Graphs
    with Neeldhara Misra, Fahad Panolan, Venkatesh Raman, and Saket Saurabh
    in Algorithmica (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]

  In Conferences
  • 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.

  Theses
  • Parameterized Algorithms for Graph Modification Problems [pdf]
    PhD thesis

  • Kernel Lower Bounds: A Survey [pdf]
    Master's thesis