Colloquium d’Informatique de Sorbonne Université
Hans Bodlaender, Utrecht University
Thursday, October 10, 2024 18:00
Amphi 25 Sorbonne University - Faculté des Sciences
Parameterized Algorithms and Complexity Classes
Hans Bodlaender is a full professor in the area of Algorithms and Complexity at Utrecht University, the Netherlands. His work focuses on parameterized algorithms and complexity, and algorithms for graphs and networks. Much of his work was on width parameters for graphs, in particular on the notion of treewidth. He received in 2014 and in 2024 the EATCS-IPEC Nerode Prize, and in 2024 the WG Test-of-Time award.
Abstract
Many computationally hard problems become easier when some aspect of the input or requested answer is small. In the field of parameterized algorithms, the complexity of computational problems is studied under the lens where a parameter in the input is considered significantly smaller than the input size. In this talk, some of the main concepts of the field are surveyed with the help of a number of examples, including the notions of fixed parameter tractability (FPT algorithms), the W-hierarchy, slicewise polynomial time (XP), kernelization, and polynomial kernels. In the second half of the talk, some recent developments are discussed: many problems that have been shown to be solvable in slicewise polynomial time (are in XP) by using dynamic programming can be shown to be complete for the newly discovered complexity classes XNLP or XALP. We look at a number of examples from the fields of logic, algorithmic graph theory, and scheduling. The completeness has consequences for the expected use of memory of algorithms for these problems.
Other information
Steering committee
Colloquium announcements
In order to be informed of future events via emails, you can
subscribe to colloquium announcements.
If you do not want to be informed anymore, you can
unsubscribe to colloquium announcements
- Year 2024 – 2025
- Year 2023 – 2024
-
Maurice Herlihy
June 25, 2024
Further Decentralizing Decentralized Finance -
Jean-Marc Jézéquel
April 04, 2024
Comment dompter la variabilité du logiciel ? -
Claire Mathieu
January 24, 2024
Vehicle routing and approximation algorithms -
David Bol
November 21, 2023
Six of the nine planetary boundaries are transgressed – How we do research in the Anthropocene?
-
Maurice Herlihy
- Year 2022 – 2023
- Year 2021 – 2022
- Year 2020 – 2021
- Year 2019 – 2020
- Year 2018 – 2019
-
Cláudio T. Silva
June 11, 2019
Urban Data Science -
Sébastiano Vigna
May 06, 2019
Four degrees of separation (and how we did it) -
Hugo Gimbert
March 19, 2019
Les algorithmes de Parcoursup -
Julie Grollier
February 05, 2019
Nanodevices for Bio-inspired Computing -
Jacques Pitrat
November 20, 2018
L'IA forte -
James Larus
October 23, 2018
Programming Non-Volatile Memory
-
Cláudio T. Silva
- Year 2017 – 2018
-
Eric Horvitz
June 20, 2018
AI Aspirations and Advances -
Justine Cassell
May 15, 2018
Designing Bots, Virtual Humans, and Other Systems that Can Hold up Their End of the Conversation -
Léon Bottou
March 06, 2018
Une approche géométrique de l'apprentissage non supervisé -
Jean-Luc Schwartz
January 16, 2018
Modélisation cognitive des unités de la parole -
Timothy Roscoe
November 30, 2017
The Trouble with Hardware
-
Eric Horvitz
- Year 2016 – 2017
-
Simon Peyton Jones
May 23, 2017
Escape from the ivory tower: the Haskell journey -
Maria Chudnovsky
April 25, 2017
Induced subgraphs and coloring -
Philippa Gardner
March 28, 2017
Understanding and Verifying JavaScript Programs -
Michel Beaudoin-Lafon
February 28, 2017
Interfaces Homme-Machine -
Marie-Paule Cani
November 22, 2016
Modélisation 3D expressive -
Richard Stallman
October 11, 2016
What Makes Digital Inclusion Good Or Bad? -
Patrick Cousot
September 29, 2016
Abstract interpretation
-
Simon Peyton Jones
- Year 2015 – 2016
-
Patrick Flandrin
June 16, 2016
« Chirps » everywhere -
Aude Billard
April 12, 2016
Robots that exceed human capabilities -
Willy Zwaenepoel
March 22, 2016
Really Big Data -
Jon Crowcroft
January 19, 2016
Cybersecurity and network measurement -
Isabelle Collet
November 24, 2015
Les informaticiennes, de la dominance de classe aux discriminations de sexe -
Xavier Leroy
October 20, 2015
Desperately seeking software perfection
-
Patrick Flandrin
- Year 2014 – 2015
-
Silvio Micali
May 26, 2015
Proofs, Secrets, and Computation -
Alessandra Carbone
April 14, 2015
The new era of biology is computational -
Serge Abiteboul
February 24, 2015
Toward personal knowledge bases -
Manuel Silva
November 25, 2014
Fluidization of discrete event models or a marriage between the discrete and the continuous -
Andrew S. Tanenbaum
October 28, 2014
MINIX 3: A Reliable and Secure Operating System
-
Silvio Micali
- Year 2013 – 2014
-
Donald Knuth
June 17, 2014
Computer Science: All Questions Answered -
Jeannette Wing
May 20, 2014
Toward a Theory of Trust in Networks of Humans and Computers -
David Patterson
May 06, 2014
Myths about MOOCs and Software Engineering Education -
Claude Berrou
March 25, 2014
L'information mentale -
Vint Cerf
March 04, 2014
On the Preservation of Digital Information -
C.A.R. (Tony) Hoare
November 26, 2013
Laws of concurrent system design -
Gilles Dowek
October 22, 2013
Are formal methods the future of air traffic control?
(Is there an autopilot on board?)
-
Donald Knuth
- Year 2012 – 2013
-
Mathieu Feuillet, Camille Couprie, Mathilde Noual
June 25, 2013
Espoirs : Winners of the 2012 Gilles Kahn prize -
Robert Sedgwick
May 23, 2013
Taking Education Online: A Unique Opportunity for the New Millenium -
Frans Kaashoek
April 18, 2013
The multicore evolution and operating systems -
Stuart Russell
January 22, 2013
Unifying logic and probability: A “New Dawn” for Artificial Intelligence? -
Georges Gonthier
November 27, 2012
Le génie mathématique, du théorème des quatre couleurs à la classification des groupes -
Gérard Berry
October 24, 2012
Le temps et les événements en informatique
-
Mathieu Feuillet, Camille Couprie, Mathilde Noual
- Year 2011 – 2012