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

A First Second Course in the Probabilistic Method

  • Date : 26 February 2024
  • Speaker: Dr. Niranjan Balachandran
  • Speaker bio: Dr. Niranjan Balachandran is presently an Associate Professor at the Department of Mathematics, IIT Bombay. He received B.Stat, M.Stat degrees from Indian Statistical Institute, and his Ph.D degree from Ohio State University. He was a Bateman Research Instructor at Caltech during 2008-2011. His research interest lies in the areas of Extremal & Probabilistic Combinatorics.
  • Venue: A01-212,213 Academic Building Sahyadri Campus
  • Details: The Department of Computer Science and Engineering, IIT Palakkad is conducting a series of lectures by Dr. Niranjan Balachandran, Associate Professor, Department of Mathematics, IIT Bombay during 26th February-1st March, 2024.
    Abstract The probabilistic method in combinatorics is more than a technique; it is a paradigm for combinatorial thinking as well. As this method now has become ubiquitous, I shall, in the course of these 5 lectures, give an introduction to slightly more sophisticated methods within the probabilistic paradigm. This includes
    • A look at the ‘Nibble’ method
    • The Regularity Lemma and Pseudorandomness
    • The method of Entropy Compression
    • The absorption technique
    We shall outline each of these with a principal application of each of these techniques. This is not a first course (hence the title), so we shall assume some basic familiarity with the basic ideas (the First Moment Method, some basic concentration phenomena etc).
    Date Time Venue Sub-topic
    26th February 02:00 PM-03:30 PM A01-212 A look at the ‘Nibble’ method
    27th February 01:30 PM-03:00 PM A01-212 The Regularity Lemma and Pseudorandomness
    28th February 02:00 PM-03:30 PM A01-213 The method of Entropy Compression
    29th February 12:00 PM-01:30 PM A01-213 The Absorption Technique
    1st March 02:00 PM-03:30 PM A01-212 The Absorption Technique (Continued)

Algebraic Algorithms and Matroid Theory

  • Date : 02 February 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.

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

  • Date : 07 August 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