A Cheat-Sheet for Hard Problems

Speaker: Neeldhara Misra

Abstract

When we think about designing algorithms, we are usually very demanding in how we go about it: we require our algorithms to be fast and accurate on all conceivable inputs. This is asking for quite a bit, and perhaps it is not surprising that we cannot afford this luxury all the time. The good news is that most of the time we can make meaningful progress by relaxing just one of these demands. One approach that tackles all of these tradeoffs at once is to take what is now called a 'multivariate approach' to the analysis of running times, which essentially involves appreciating that to describe a problem instance just in terms of its size is like describing a movie by a rating, which is unfortunate because there’s so much more nuance. And yet we report — and think about — worst-case running times in only terms of the sizes of the instances. The parameterized approach takes into account problem structure by addressing 'secondary' measurements (parameters), apart from the primary measurement of overall input size, that significantly affect problem computational complexity. The central notion of fixed parameter tractability (FPT) is a generalization of polynomial-time based on confining any non-polynomial complexity costs to a function only of these secondary measurements. In this talk, we will introduce this paradigm and illustrate its utility in theory and practice.

Bio

Neeldhara Misra is a Smt. Amba and Sri. V S Sastry Chair Associate Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. She completed her PhD from the Institute for Mathematical Sciences in 2012 in Theoretical Computer Science, and was an INSPIRE faculty fellow at the CSA department of IISc between 2013 and 2015. Her research interests include the design and analysis of algorithms in the context of problems that arise in graph theory, combinatorial games, and computational social choice. She is also interested in visualizations and other methods to communicate computational thinking at an elementary level.