Parameterized Complexity Theory and its Applications to Social Choice

Parameterized complexity offers a 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.


Simon Rey: PhD candidate at the ILLC under the supervision of Ulle Endriss and Ronald de Haan, I work in the area of computational social choice, taking a computational perspective on some collective decision-making problems.

Ronald de Haan: assistant professor at the ILLC, my research interests include the application of methods from theoretical computer science—in particular methods from (parameterized) complexity theory—to problems in artificial intelligence (AI), knowledge representation & reasoning (KRR), and computational logic.

Useful resources

The following three books are nice references for parameterized complexity and will serve as official references for the content of the lectures:

The following chapter offers a quick presentation of parameterized complexity in the context of computational social choice:


Below you will find the schedule week per week, keep in mind that time slots may vary a bit (not for the first week though).

Week 1

During the first week, we will give four lectures to give everyone the tools to understand and play with parameterized complexity

There will not be any homework or exercises to do between two lectures. You are however asked to review the lectures to make sure you assimilated everything and to go through the proofs to ensure you understand how to use the tools.

Week 2

The idea for the second week is to continue the lectures but this time with the students as presenters. Below you will find a list of the topics that can be discussed together with some references for them. Each topic is about a theoretical aspect of parameterized complexity that has not been discussed (or very lightly) in the lectures we gave. In the references you will typically find one book chapter that describes the theory of the concept and a paper showing applications of the technique in the context of computational social choice.

The steps that you have to complete are the following ones.

  1. Pair up with another student to form a team of two persons.
  2. Select a topic you want to work on, let's see if several teams want the same subjects.
  3. Once teams and topics have been arranged, prepare your presentation with your partner.
  4. Select a time slot for your presentation.
  5. Finally, give the presentation (what a surprise!).

The presentation should be around 30 minutes long, 15 extra minutes will be scheduled afterwards for questions. The format is not fixed, but, you are asked to present two things (each of them taking roughly half of the presentation): the theoretical aspect of your topic (definitions, interesting results, etc...) and an example of a nice application from the computational social choice literature. As you can see, the two parts of the presentation correspond to the two type of references we provided you with.

Below you can find a list of the topics, together with their references.

To decide who will do which topic, we will use some kinds of algorithms supposed to generate a fair outcome. For this to work we need to know your preferences. By the third of June at 19:00, we ask you to write us an email detailing your preferences. Here is what we need: You are allocated 60 indivisible points. For each of the six topics above, indicate us how many points you give to the topic (that represents somehow your happiness for dealing with the topic). You can choose to give 0 point to a topic, but you must give non-0 score to at least 3 topics. All the points must be allocated.

The schedule for the presentations is as follows:

At the end of the last presentation on Friday, we will take a bit of time to discuss the papers you will have to submit.

Week 3

During the third week, we will have meetings with all the students to discuss their ideas and progress for their papers. Each meeting will be 30 minutes long and will be scheduled during one of the following time slot:

Other details will be arranged later.

By the end of Tuesday the 15th, we ask you to send us an email containing the name of the persons you will be writing the paper with (if you are a team) or your own name (if you are alone) and the idea that you want to follow. We want to approve your ideas before you explore them in depth.

Week 4

Last week is dedicated to the writing up of the paper. We will not plan anything during that week but if you need anything, please contact us.

The deadline to submit the paper is by the end of this week, to be exact on the 25th at 19:00.

Recap on the deadlines

Here is a list of the deadlines for the projects:

The final paper

The final delivery for this project is a short paper that you will write on a topic of your choice. The content of the paper can be twofold. It can be a thorough analysis of an existing work that you explain in your own words. You can also choose to develop an original idea you had on the topic and present your findings. The second option might look scary but keep in mind that we do not expect you to have ground-breaking results after such a short project. Presenting the direction you followed as well as few findings is the kind of outcome we expect.

Any topic related to parameterized complexity will be ok. We do still ask you to submit your topic for approval in the middle of the third week.

You are free to write the final paper alone or as a team of two. The rules are the same, although our expectations will be higher if two persons are involved.

The paper should be typeset in LaTeX, using the IJCAI guidleines. It should look like a research article and thus should include an introduction with the motivation of the study, a (brief) review of the literature, some preliminaries explaining all the notations you will be using, the main findings and a conclusion. The paper should not exceed 6 pages including the references. Note that it is more than fine if you submit less than 6 pages, we value precision and conciseness more than anything! We strongly encourage you to read and follow the advice on writing a paper put together by Ulle Endriss.

The deadline for submitting your paper is on the 25th of June at 19:00. To submit it, email both of us with an appropriate header and the PDF file of your paper attached.


At the end of the project, each student will receive a fail or pass grade. Two deliveries are expected for this project: the presentation and the final paper. Each of them will be graded with a fail or pass grade. The final grade of the project is the conjunction of these two grades.