Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Graph
Search

Cours

MATH-683: Fine-grained and parameterized complexity

Résumé

The classical distinction between polynomial time solvable and NP-hard problems is often too coarse. This course covers techniques for proving more fine-grained lower and upper bounds on complexity of computational problems.

Séances de cours

Enseignant·e

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Source officielle

https://edu.epfl.ch/coursebook/fr/fine-grained-and-parameterized-complexity-MATH-683

Page Moodle

http://go.epfl.ch/MATH-683

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Résumé

Séances de cours

Enseignant·e

Friedrich Eisenbrand

Source officielle

https://edu.epfl.ch/coursebook/fr/fine-grained-and-parameterized-complexity-MATH-683

Page Moodle

http://go.epfl.ch/MATH-683

À propos de ce résultat

Proximité ontologique

Informatique théorique

Theory of computation: Théorie de la complexité (informatique théorique)

Mathématiques

Mathématiques discrètes: Théorie des graphes

Cours associés (31)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computating in an axiomatic way. We introduce the notions of quantum bits, gates, and circuits. We introduce themost important quantum algorithms. We also touch upon error-correcting codes. This course is indep ...

Afficher plus