Ramanujan Auditorium

Coping with Intractability Using Parameters

Saket Saurabh

IMSc, Chennai

One of the greatest achievements in theoretical computer science is the development of NP-completeness theory. NP-completeness theory provides a solid and convincing foundation for the study of computationally intractable problems. However, the theory does not make obsolete the pressing need for solving these hard problems because of their practical importance. Many approaches have been proposed, including polynomial-time approximation algorithms, randomized algorithms, and heuristic algorithms. The focus of this talk will be another approach to cope with NP-completeness, namely, fixed-parameter tractability (FPT for short). The talk will be in the form of a story -- accessible to most.

This event will also celebrate the Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 in Mathematical Sciences awarded to Prof. Saket Saurabh.

High tea will be served after the lecture at 1715 Hrs.

More information on Azadi Ka Amrit Mahotsav events conducted by IMSc is available at: www.imsc.res.in/akam/