AN INTRODUCTION TO PARAMETERIZED COMPLEXITY

AN INTRODUCTION TO PARAMETERIZED COMPLEXITY

Date
9 – 12 April 2018
h. 10.00-13.00
Registration
No fee.
Registration required.
Location
Campus Nord, Edifici Ω, Room: S215
UPC
SHORT DESCRIPTION
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.

Date
9 – 12 April 2018
h. 10.00-13.00
Registration
No fee.
Registration required.
Location
Campus Nord, Edifici Ω, Room: S215
UPC
SHORT DESCRIPTION
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.

Course organized by Servei d’Estadística Aplicada with the support of the BGSMath, through the ”María de Maeztu” Programme for Units of Excellence in R&D” (MDM‐2014‐0445).

Lecturer
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
Prof. Dimítrios M. Thilikós Touloupas received his PhD from the Department of Computer Engineering and Informatics of the University of Patras in 1996. Currently (2018) he is CNRS researcher at LIRMM and Professor at the Department of Mathematics of NKUA. Also he is currently visiting the CS department of UPC as a research assistant. His research includes contributions in several fields of Theoretical Computer Science and Discrete Mathematics with contributions in Parameterized Computation and Graph Theory. In particular, his results are related to Structural Graph Theory, Graph Decompositions, Approximation Algorithms, Probabilistic Methods, Graph Searching Games, and Graph Homomorphisms. He also has contributions to applied areas such as Distributed Computing, Bioinformatics, and Data Mining. He has published 146 papers, among which 40% during the last 5 years.

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.