An Introduction to Multivariate Algorithmics / Parameterized Complexity for the Practical Computer Scientist and Algorithms Engineer

The talk will focus on concrete practical motivations, examples and perspectives that have driven and continue even more forcefully to drive the development of the parameterized / multivariate theory of algorithms and complexity. The objective is not to describe the details of the theory, but rather to concretely motivate it. The talk is aimed at practical computer scientists who have often been rightly skeptical that algorithms and complexity theory has anything much to offer. The advent of multivariate algorithmics opens up many new ways in which a mathematically disciplined theory of algorithms and complexity can be deployed to strengthen practical computing. For example, methods of exploiting relevant secondary measurements of input structure have been important in Bio and Medical Informatics data-mining.

Speaker Bio

Prof. Fellows received his PhD from the University of California, San Diego, in 1985, and has since held academic posts in the USA, Canada, New Zealand and Australia. In 2006 he received the prestigious Humboldt Research Prize for his foundational work on parameterized complexity. He is an Associate Editor for the ACM Transactions on Algorithms and the Journal of Computer and System Sciences. In 2014 he was elected one of the ten Inaugural Fellows of the European Association for Theoretical Computer Science, and an Honorary Fellow of the Royal Society of New Zealand (one of 230 since 1870; the first computer scientist on that list). His work has been cited more than 12,000 times.