2nd Semester 2020/21: Parameterized Complexity Theory and its Applications to Social Choice

Instructors

Simon Rey and Ronald de Haan

ECTS

6

Description

Parameterized complexity offers a more fine-grained analysis when studying computational complexity (the amount of resources required to solve a problem). It allows to classify computational problems based on how hard they are to solve with respect to some parameters. In that sense, it leads to a better understanding of what makes certain problems hard to solve. At the same time, it opens new perspectives on how to efficiently solve hard problems in real-life settings (when some parameters are small for instance).
The aim of this project is to study the theory of parameterized complexity and how it can be applied. For the applications we will mainly discuss problems arising in the study of computational social choice.

Organisation

The project will be run over 4 weeks. During the first week, we will give several lectures (probably 4) to give everyone the tools to understand and play with parameterized complexity. In the second week, students will present some more advanced topics taken from research articles or book chapters. The last two weeks will be devoted to the writing up of the outcome of the project: a short paper on a topic chosen by the students.

Prerequisites

Prior knowledge in complexity theory and/or computational social choice will make it easier for the students but is not required. Good mathematical maturity is needed.

Assessment

The students will be assessed based on two things: the presentation during the second week and the final paper. The presentation will consist of a talk about a research article or a book chapter on the topic (the exact duration will be decided later, it will be between 20 and 45 minutes). We will provide a list of papers/chapters from which students will choose what they want to present. The final outcome will be a short paper written by the students on a topic they choose. It can for instance consist of a parameterized complexity investigation of a given problem, or a more theoretical reflection on parameterized complexity.

References

The following two books are nice references for parameterized complexity (and everything we will cover also is presented there):
- Parameterized Complexity Theory, J. Flum and M. Grohe, Springer-Verlag Berlin Heidelberg, 2006
- Parameterized Algorithms, M. Cygan et al., Springer-Verlag Berlin Heidelberg, 2015
The following chapter offers a quick presentation of parameterized complexity in the context of computational social choice:
- Having a Hard Time? Explore Parameterized Complexity!, B. Dorn and I. Schlotter, Chapter 11 in Trends in Computational Social Choice, Editor: Ulle Endriss, 2017