Talk Series

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
• Abstract: 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.