AN INTRODUCTION TO PARAMETERIZED COMPLEXITY
AN INTRODUCTION TO PARAMETERIZED COMPLEXITY
h. 10.00-13.00
Registration required.
UPC
Parameterized complexity was introduced in the 90’s by Downey and Fellows and proposed a more refined analysis of computational problems. The key idea is to study the different ways key secondary parameters may be interleaved with input size in the computational complexity of algorithms.
Such a study revealed opportunities for designing algorithms that can still be considered efficient under a more loose, but still legitimate, concept of efficiency. This induced the study of computational problems as ”bivariate entities” where, apart from the input size, the second variable is a parameter that measures certain structural particularities, especially those that are common in real applications.
Parameterized complexity theory is now a mature field of Theoretical Computer Science and has developed a wealth of techniques for for designing parameterized algorithms (i.e., upper bounds) but also for proving that such algorithms probably do not exist (i.e., lower bounds). For proving lower bounds, Downey and Fellows introduced a hierarchy of parameterized complexity classes and suitable
concepts of problem reducibility that permitted the systematic classification of numerous computational problems according to their parameterized complexity.
This course covers the foundational concepts of this theory from the point of view of the lower bounds. The course covers the concept of problem parameterization, explains ‘why and how’ this induced the definition of the parameterized complexity hierarchy, and provides some links of this theory to the classical complexity theory.
h. 10.00-13.00
Registration required.
UPC
Parameterized complexity was introduced in the 90’s by Downey and Fellows and proposed a more refined analysis of computational problems. The key idea is to study the different ways key secondary parameters may be interleaved with input size in the computational complexity of algorithms.
Such a study revealed opportunities for designing algorithms that can still be considered efficient under a more loose, but still legitimate, concept of efficiency. This induced the study of computational problems as ”bivariate entities” where, apart from the input size, the second variable is a parameter that measures certain structural particularities, especially those that are common in real applications.
Parameterized complexity theory is now a mature field of Theoretical Computer Science and has developed a wealth of techniques for for designing parameterized algorithms (i.e., upper bounds) but also for proving that such algorithms probably do not exist (i.e., lower bounds). For proving lower bounds, Downey and Fellows introduced a hierarchy of parameterized complexity classes and suitable
concepts of problem reducibility that permitted the systematic classification of numerous computational problems according to their parameterized complexity.
This course covers the foundational concepts of this theory from the point of view of the lower bounds. The course covers the concept of problem parameterization, explains ‘why and how’ this induced the definition of the parameterized complexity hierarchy, and provides some links of this theory to the classical complexity theory.
Contents
- The idea of parameterization
- The class FPT
- Examples of FPT-algorithms
- FPT-reductions
- The classes para-NP, XP
- The classes W[P] and W[SAT]
- The W-hierarchy, alternative definitions
- Hardness for the W-hierarchy
- Εxponential Time Hypothesis
- Sparsification Lemma
Lecturer's short bio
His teaching has been focused on the Mathematical Foundations of Computer Science. He taught many graduate and undergraduate courses at universities or research centers in Canada, in Spain, France, Belgium, Greece, and Norway. He gave courses on Complexity Theory, Recursion Theory, Automata Theory, Algorithms, Combinatorics, Graph Theory, and Programming. He has also designed and taught several mini-courses on thematic areas of his expertise including 4 tutorials at seasonal schools at the margin of international conferences and workshops. He has given 61 seminar talks in several research centers and universities. He has supervised 5 PhD-thesis and 18 MSc Thesis.
He has has been 11 times the main organizer of conferences/worshops. He has been 32 times a PC member of conferences/worshops and he has been charing 2 of them. In total, he has given 10 invited talks in conferences/worshops. Finally, he has been the editor or LNCS volumes 6410 and 7535, of DAM volume 199, and TCS volumes 399, 412, and 655.
In 2015 he received the EATCS Nerode Prize for his contribution to Parameterized Computation.