Séminaire CAESAR
de combinatoire additive
Séance du jeudi 26 juin 2014
(11 heures, UPMC Paris 6 Jussieu, couloir 15-16, salle 101):
Antoine JOUX
(LIP6, UPMC)
Algorithmes de décompositions: subset sum problem
et décodage de codes binaires aléatoires
Dans cet exposé, nous présenterons une méthode
probabiliste de résolution de problèmes combinatoires additifs
comme le subset-sum problem ou le décodage de codes binaires
aléatoires. Ces algorithmes permettent, par exemple, de
réduire la complexité de résolution d'un
subset-sum de densité 1 à n éléments de 2^(n/2)
à 2^(0,337 n).
Malheureusement, on ne sait en garantir le fonctionnement que
pour des instances aléatoires du subset-sum.
Retour à la page d'accueil du
séminaire