This page lists all the talks series delivered at the department of Computer Science and Engineering, IIT Palakkad.

Flow-Augmentation: recent advances in parameterized (weighted) cut problems

  • Date : August 07, 2023
  • Speaker: Dr. Roohani Sharma
  • Speaker bio: Roohani Sharma is a Lise Meitner Post-doctoral fellow at the Max Planck Institute for Informatics, SaarbrĂĽcken, Germany. She received her PhD from the Institute of Mathematical Sciences, Chennai under the supervision of Saket Saurabh, for which she received 'Honorable mention at ACM India Doctoral Dissertation Award 2021'. Prior to that, she did her Masters in Computer Science at the Chennai Mathematical Institute for which she received the Gold Medal for Excellence in Computer Science. Her B.Tech was in Computer Science and Engineering from Shri Mata Vaishno Devi University, Jammu and Kashmir.
  • Venue: Room 303, Nila Campus
  • Details: The Department of Computer Science and Engineering, IIT Palakkad organized a mini lecture series on “Flow-Augmentation: recent advances in parameterized (weighted) cut problems” on Monday, August 7, 2023. The talks should be self-contained and will only require some basic familiarity with the design of algorithms. All are welcome to attend the talks, which are to be held at Room 303, Nila. The rough schedule is as follows :
    • Part 1: 10 am to 11:30 am (Tea and Snacks: 11:30 am to 11:45 am)
    • Part 2: 11:45 am to 1 pm
    • Part 3: 2:30 pm to 4 pm
    Summary: Network flow and cut problems are well-known classical problems in combinatorial optimization. In this series of talks, we will see how some of the very important questions in the study of parameterized cut problems were resolved using the very recently introduced tool of Flow Augmentation. We start by revisiting the classical (greedy) tools like Important Cuts and Shadow Removal that existed before flow-augmentation and the barriers they imposed in our understanding of the parameterized cut world. We then discuss the powerful tool of Flow-Augmentation which appeared in 2021&2022, followed by stating results that exhibit the power of this new tool. In particular, we focus on how Flow-augmentation yields parameterized dichotomy for (Weighted) Boolean MinCSPs. We then discuss how some fundamental weighted cut problems like Weighted Multicut and Weighted (Subset) Directed Feedback Arc Set, reduce to the tractable class of this Weighted Boolean MinCSP, thereby showing that these problems are fixed-parameter tractable.
    Link to the slides from the talk

Algebraic Algorithms and Matroid Theory

  • Date : Feb 02 to Feb 06, 2023
  • Speaker: Prof. Saket Saurabh
  • Speaker bio: Prof. Saket Saurabh is a Professor of Theoretical Computer Science at the Institute of Mathematical Sciences and Professor of the Department of Informatics at University of Bergen. Prof. Saket Saurabh is an awardee of the prestigious Shanti Swarup Bhatnagar Prize for Science and Technology in Mathematical Sciences in 2021 and he is known for his fundamental contributions to the area of parameterized complexity including procedures for obtaining algorithmic lower bounds, and meta-theorems on preprocessing.
  • Venue: Board Room, Ahalia Campus
  • Details: The Department of Computer Science and Engineering, IIT Palakkad organized a mini lecture series on Algebraic Algorithms and Matroid Theory from Feb 2 to Feb 6, 2023. The lectures were delivered by Prof. Saket Saurabh. The lectures introduced the audience to matroid theory and discussed algebraic algorithms for classical problems on matroids. The common theme in these algorithms was observed to be applicability of matrix rank computation. Then the focus shifted to algorithms for graph-theoretic problems using rank computation of certain matrices associated with graphs. This led to the discussion of elegant algebraic algorithms for finding maximum matchings in bipartite graphs and general graphs. The series ended with an interesting interplay among matroid representation, representative families for set systems and parameterized algorithms for NP-complete problems on graphs.