CINXE.COM

<!DOCTYPE HTML> <html> <head> <meta charset="utf-8"> <meta http-equiv="content-type" content="text/html; charset=windows-1252" /> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta http-equiv="x-ua-compatible" content="ie=edge"> <meta name="revisit-after" content="7 days"> <title>Pranabendu Misra</title> <meta name="description" content="Homepage of Pranabendu Misra"> <meta name="keywords" content="pranabendu, pranab, pranav, pranabendu misra, pranab misra, pranav misra, pranabendu mishra, pranab mishra, pranav mishra"/> <link rel="stylesheet" href="main.css">  <link rel="preconnect" href="https://fonts.googleapis.com"> <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin> <link href="https://fonts.googleapis.com/css2?family=STIX+Two+Text:ital,wght@0,400;0,500;0,600;0,700;1,400;1,500;1,600;1,700&display=swap" rel="stylesheet"> <script src="mainScript.js"></script> </head> <body> <main>   <div class="topnav"> <div class="centerDivName">  <a class="myname" href="index.html">Pranabendu Misra</a> <a href="javascript:void(0);" class="toggleIcon" onclick="toggleMenu()"> <span class="hamburger"></span> </a> </div> <div class="centerDiv"> <ul class="topnav-list"> <li><a class="tablinks" href="short-cv.html">CV</a></li> <li><a class="tablinks" href="index.html#publications" onclick="gotoHashTag(event, '#publications')" >Publications</a></li> <li><a class="tablinks" href="index.html#teaching" onclick="gotoHashTag(event, '#teaching')" >Teaching</a></li> <li><a class="tablinks" href="index.html#contact" onclick="gotoHashTag(event, '#contact')" >Contact</a></li> <li><a class="tablinks" href="index.html#links" onclick="gotoHashTag(event, '#links')" >Links</a></li> </ul> </div> <div class="topnavBorder"></div> </div> <div class="content"> <div class="news"><b>News: </b> <i> papers accepted to SODA'24 and ITCS'24 </i> <a class='tablinks' href='news.html'>(more...)</a></div> </div>  <p><img src="myPhoto.jpg" alt="photo" id="myPhoto" style="float: right;" /></p> <p>I am an Assistant Professor in Computer Science at the <a href="https://www.cmi.ac.in/" target="_blank">Chennai Mathematical Institute (CMI)</a>, India.</p> <p>In the recent past, I was a postdoctoral fellow in the Algorithms and Complexity department at the <a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/" target="_blank">Max Planck Institute for Informatics</a>, Saarbrucken, Germany. Earlier, I was a researcher in the Algorithms group at the Department of Informatics, <a href="https://www.uib.no/en/rg/algo/55502/group-members" target="_blank">University of Bergen</a>, Norway.</p> <p>I obtained my PhD in Computer Science, advised by Prof. <a href="https://www.imsc.res.in/saket_saurabh" target="_blank">Saket Saurabh</a>, from the <a href="https://www.imsc.res.in/" target="_blank">Institute of Mathematical Sciences (IMSc)</a>, India and my masters and undergraduate degree from <a href="https://www.cmi.ac.in/" target="_blank">CMI</a> in Mathematics and Computer Science.</p>  <h2 id="grants-awards">Grants, Awards …</h2> <ul> <li>Research Project grant Fujitsu 2023 <ul> <li>jointly with Priyavrat Deshpande and Nithin Varma</li> </ul></li> <li>Google India Research Award 2022</li> <li>SERB (India) Startup Research Grant (SRG) 2022</li> </ul> <h2 id="research-interests">Research Interests</h2> <p>Algorithms and their applications.</p> <p>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.</p> <h2 id="publications">Publications</h2>  <p>(Also available at <a href="https://dblp.org/pers/hd/m/Misra:Pranabendu" target="_blank">DBLP</a> and <a href="https://scholar.google.com/citations?user=nk4cGOYAAAAJ&hl=en" target="_blank">Google Scholar</a>.)</p> <ul> <li>Meta-theorems for Parameterized Streaming Algorithms <ul> <li>with Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh and Meirav Zehavi</li> <li><strong>SODA 2024</strong></li> </ul></li> <li>Kernelization of Counting Problems <ul> <li>with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi</li> <li><strong>ITCS 2024</strong></li> </ul></li> <li>Parameterized Approximation Algorithms for Weighted Vertex Cover <ul> <li>with Soumen Mandal, Ashutosh Rai and Saket Saurabh</li> <li><strong>LATIN 2024</strong></li> </ul></li> </ul> <h2 id="section"></h2> <ul> <li>An ETH-Tight Algorithm for Bidirected Steiner Connectivity.<br /> <ul> <li>with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi<br /> </li> <li><strong>WADS 2023</strong></li> </ul></li> <li>A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands <ul> <li>Jørgen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh</li> <li><strong>ESA 2023</strong></li> </ul></li> </ul> <h2 id="section-1"></h2> <ul> <li>A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs <ul> <li>with Daniel Marx, Daniel Neuen and Prafullkumar Tale</li> <li><strong>SODA 2022</strong></li> </ul></li> </ul> <h2 id="section-2"></h2> <ul> <li>Improving EFX Guarantees through Rainbow Cycle Number <ul> <li>with Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn and Ruta Mehta</li> <li><strong>EC 2021</strong></li> </ul></li> <li>Strong Connectivity Augmentation is FPT <ul> <li>with Kristine Vitting Klinkby and Saket Saurabh</li> <li><strong>SODA 2021</strong></li> </ul></li> <li>FPT Approximation for FPT Problems <ul> <li>with Daniel Lokshtanov, MS Ramanujan, Saket Saurabh and Meirav Zehavi</li> <li><strong>SODA 2021</strong></li> </ul></li> </ul> <h2 id="section-3"></h2> <ul> <li>An Exponential Time Parameterized Algorithm for Planar Disjoint Paths <ul> <li>with Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh and Meirav Zehavi</li> <li><strong>STOC 2020.</strong></li> </ul></li> <li>Fault Tolerant Subgraphs with Applications in Kernelization <ul> <li>with William Lochet, Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi</li> <li><strong>ITCS 2020.</strong></li> </ul></li> <li>2-Approximating Feedback Vertex Set in Tournaments <ul> <li>with Daniel Lokshtanov, Joydeep Mukherjee, Geevarghese Philip, Fahad Panolan, Saket Saurabh</li> <li><strong>SODA 2020.</strong></li> </ul></li> <li>On the Complexity of Recovering Incidence Matrices <ul> <li>with Ramanujan M. S., Petr Golovach and Fedor Fomin</li> <li><strong>ESA 2020.</strong></li> </ul></li> <li>A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion <ul> <li>with Daniel Lokshtanov, Fahad Panolan, Geevarghese Philip and Saket Saurabh</li> <li><strong>ICALP 2020.</strong></li> </ul></li> <li>Quick Separation in Chordal and Split Graphs <ul> <li>with Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani Sharma</li> <li><strong>MFCS 2020.</strong></li> </ul></li> <li>Parameterized Complexity of Directed Spanner Problems <ul> <li>with Fedor Fomin, Petr Golovach, William Lochet, Saket Saurabh and Roohani Sharma</li> <li><strong>IPEC 2020</strong></li> </ul></li> </ul> <h2 id="section-4"></h2> <ul> <li>Popular Matching in the Roommates Setting is NP-hard <ul> <li>with Sushmita Gupta, Saket Saurabh, and Meirav Zehavi</li> <li><strong>SODA 2019</strong></li> </ul></li> <li>Interval Vertex Deletion Admits a Polynomial Kernel <ul> <li>with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi</li> <li><strong>SODA 2019</strong></li> </ul></li> <li>An Erdős-Pósa Theorem on Neighborhoods and Domination Number <ul> <li>with Jayakrishnan Madathil and Saket Saurabh</li> <li><strong>COCOON 2019</strong></li> </ul></li> </ul> <h2 id="section-5"></h2> <ul> <li>Parameterized Algorithms for Survivable Network Design with Uniform Demands <ul> <li>with Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Ramanujan M. S., Saket Saurabh and Meirav Zehavi</li> <li><strong>SODA 2018</strong></li> </ul></li> <li>Erdos-Posa Property of Obstructions to Interval Graphs <ul> <li>with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi</li> <li><strong>STACS 2018</strong></li> </ul></li> <li>Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity <ul> <li>with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi</li> <li><strong>ITCS 2018</strong></li> </ul></li> <li>Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems <ul> <li>with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi</li> <li><strong>APPROX 2018</strong></li> <li><strong>Journal</strong>: ACM Transactions on Algorithms, 2020.</li> </ul></li> <li>Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number <ul> <li>with Roohani Sharma, Saket Saurabh and Meirav Zehavi</li> <li><strong>FSTTCS 2018</strong></li> </ul></li> <li>Exploring the Kernelization Borders for Hitting Cycles <ul> <li>with Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh and Saket Saurabh</li> <li><strong>IPEC 2018</strong></li> </ul></li> <li>Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized <ul> <li>with Pallavi Jain and Lawqueen Kanesh</li> <li><strong>CSR 2018</strong></li> <li><strong>Journal</strong>: Theory of Computing Systems, 2020.</li> </ul></li> <li>An FPT Algorithm for Contraction to Cactus. <ul> <li>with R. Krithika and Prafullkumar Tale.</li> <li><strong>COCOON 2018</strong></li> </ul></li> </ul> <h2 id="section-6"></h2> <ul> <li>Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion <ul> <li>with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.</li> <li><strong>SODA 2017</strong></li> <li><strong>Journal</strong>: ACM Transactions on Algorithms, 2019.</li> </ul></li> <li>Fast Exact Algorithms for Survivable Network Design with Uniform Requirements. <ul> <li>with Akanksha Agarwal, Fahad Panolan and Saket Saurabh.</li> <li><strong>WADS 2017</strong></li> </ul></li> <li>Derandomization of Transversal Matroids and Gammoids in Moderately Exponential Time. <ul> <li>with Fahad Panolan, M.S. Ramanujan and Saket Saurabh.</li> <li><strong>COCOON 2017</strong></li> <li><strong>Journal</strong>: Theoretical Computer Science, 2020.</li> </ul></li> <li>Hitting Selected (Odd) Cycles. <ul> <li>with Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.</li> <li><strong>Journal</strong>: In SIAM Journal of Discrete Mathematics 31(3):1581-1615 (2017).</li> </ul></li> <li>Lossy Kernels for Graph Contraction Problems <ul> <li>with R Krithika, Ashutosh Rai and Prafullkumar Tale.</li> <li><strong>FSTTCS 2016</strong></li> </ul></li> <li>Deterministic Truncation of Linear Matroids. <ul> <li>with Daniel Lokshtanov, Fahad Panolan and Saket Saurabh.</li> <li><strong>ICALP 2015</strong></li> <li><strong>Journal</strong>: ACM Transactions on Algorithms, 2018.</li> </ul></li> <li>Reducing Rank of the Adjacency Matrix by Graph Modification. <ul> <li>with S. M. Meesum and Saket Saurabh</li> <li><strong>COCOON 2015</strong></li> <li><strong>Journal</strong>: Theoretical Computer Science 654:70-79 (2016).</li> </ul></li> <li>Finding Even Subgraphs Even Faster. <ul> <li>with Prachi Goyal, Fahad Panolan, Geevarghese Philip and Saket Saurabh.</li> <li><strong>FSTTCS 2015</strong></li> <li><strong>Journal</strong>: Journal of Computer and System Sciences, 2018.</li> </ul></li> <li>Parameterized Algorithms to Preserve Connectivity. <ul> <li>with Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan and Saket Saurabh.</li> <li><strong>ICALP 2014</strong></li> </ul></li> <li>Faster Graph Bipartization <ul> <li>with Sudeshna Kolay, M. S. Ramanujan and Saket Saurabh.</li> <li><strong>MFCS 2014</strong></li> <li><strong>Journal</strong>: Journal of Computer and System Sciences, 2020.</li> </ul></li> <li>Faster Exact Algorithms for Some Terminal Set Problems. <ul> <li>with Rajesh H. Chitnis, Fedor V. Fomin, Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.</li> <li><strong>IPEC 2013</strong></li> <li><strong>Journal</strong>: Journal of Computing and System Sciences 88:195-207 (2017).</li> </ul></li> <li>Faster Parameterized Algorithms for Deletion to Split Graphs <ul> <li>with Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Fahad Panolan, Ashutosh Rai and M. S. Ramanujan.</li> <li><strong>SWAT 2012</strong></li> <li><strong>Journal</strong>: Algorithmica 71(4): 989-1006 (2015).</li> </ul></li> <li>Parameterized Algorithms for Even Cycle Transversal <ul> <li>with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.</li> <li><strong>WG 2012</strong></li> </ul></li> <li>A polynomial kernel for Feedback Arc Set on bipartite tournaments. <ul> <li>with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.</li> <li><strong>ISAAC 2011</strong></li> <li><strong>Journal</strong>: Theory of Computing Systems 53(4):609-620 (2013).</li> </ul></li> </ul> <h3 id="manuscripts">Manuscripts</h3> <ul> <li>Deterministic Representation of Gammoids in Quasipolynomial time with Applications <ul> <li>with Rohit Gurjar, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi</li> </ul></li> <li>A Brief Note on Single Source Fault Tolerant Reachability <ul> <li>with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi</li> </ul></li> <li>On Fault Tolerant Feedback Vertex Set</li> </ul> <h3 id="thesis">Thesis</h3> <ul> <li><a href="https://www.imsc.res.in/xmlui/handle/123456789/408" target="_blank">PhD Thesis</a>: Parameterized Algorithms for Network Design.</li> </ul> <h2 id="teaching">Teaching</h2> <ul> <li>[Approximation Algorithms] <ul> <li>Spring 2024, Chennai Mathematical Institute</li> </ul></li> <li><a href="https://www.cmi.ac.in/~pranabendu/genai24/">Introduction to Generative Models</a> <ul> <li>Spring 2024, Chennai Mathematical Institute</li> <li>with Dinesh Kirthivasan (Kantar)</li> </ul></li> <li><a href="https://www.cmi.ac.in/~pranabendu/aml23/">Advanced Machine Learning</a> <ul> <li>Autumn 2023, Chennai Mathematical Institute</li> </ul></li> <li><a href="https://www.cmi.ac.in/~madhavan/courses/dmml2023">Data Mining and Machine Learning</a> <ul> <li>Spring 2023, Chennai Mathematical Institute</li> <li>with <a href="https://www.cmi.ac.in/~madhavan">Madhavan Mukund</a></li> </ul></li> <li><a href="https://www.cmi.ac.in/~pranabendu/aml22/">Advanced Machine Learning</a> <ul> <li>Autumn 2022, Chennai Mathematical Institute</li> </ul></li> <li><a href="https://www.cmi.ac.in/~pranabendu/approx22/">Approximation Algorithms</a> <ul> <li>Spring 2022, Chennai Mathematical Institute</li> <li>with <a href="https://www.cmi.ac.in/~nithinvarma/">Nithin Varma</a></li> </ul></li> <li><a href="https://www.cmi.ac.in/~madhavan/courses/aml2021/">Advanced Machine Learning</a> <ul> <li>Autumn 2021, Chennai Mathematical Institute</li> <li>with <a href="https://www.cmi.ac.in/~madhavan">Madhavan Mukund</a></li> </ul></li> <li>Theoretical Foundations of Machine Learning <ul> <li>Autumn 2021, Chennai Mathematical Institute</li> <li>with <a href="https://www.cmi.ac.in/~kv/">K V Subrahmanyam</a></li> </ul></li> <li><a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms">Parameterized Algorithms</a> <ul> <li>Summer 2020, Max-Planck Institute for Informatics</li> <li>with <a href="https://people.mpi-inf.mpg.de/~dmarx/">Daniel Marx</a> and <a href="https://people.mpi-inf.mpg.de/~wellnitz/">Philip Wellnitz</a></li> </ul></li> <li><a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer19/dist-seq-algo">Distributed and Sequential Graph Algorithms</a> <ul> <li>Summer 2019, Max-Planck Institute for Informatics</li> <li>with <a href="https://sites.google.com/view/saeedamiri/home">Saeed Amiri</a> and <a href="https://people.mpi-inf.mpg.de/~cosmina/">Cosmina Croitoru</a></li> </ul></li> </ul> <h2 id="contact">Contact</h2> <h3 id="email">Email</h3> <p><code>pranabendu.m [__A_T___] gmail.com</code><br /> <code>pranabendu@cmi.ac.in</code></p> <h3 id="postal-address">Postal address</h3> <pre><code>Chennai Mathematical Institute H1, SIPCOT IT Park, Siruseri Kelambakkam, Chennai 603103 India</code></pre> <hr /> <h1 id="links">Links</h1> <ul> <li><a href="tcs-conf.html">A list of Theoretical Computer Science Conferences</a></li> </ul> <h2 id="section-7"></h2> <h2 id="section-8"></h2>  </main> </body> </html>