Mardi 6 Octobre


Retour à la vue des calendrier
Mardi 6 Octobre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Johnson-Lindenstrauss Lemma in Linear and Integer Feasibility
Description: Leo Liberti The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming, which cannot be expressed only in function of Euclidean distances.

Leo Liberti, Vu Khac Ky, Pierre-Louis Poirion
CNRS LIX, Ecole Polytechnique, Palaiseau, France
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Calculabilité et pavages
Description: Pascal Vanier Les pavages, ou sous-shifts de type fini sont des ensembles de coloriages du plan vérifiant des contraintes locales en nombre fini. Nous nous intéresserons en particulier au problèmes d'isomorphisme entre sous-shifts, connu sous le nom de conjugaison et plus particulièrement aux invariants de conjugaison, qui sont des "objets" permettant de caractériser certains aspects des sous-shifts. Nous donnerons en particulier des caractérisations calculatoires de ces derniers qui permettront de voir les liens intimes qui lient pavages et classes de complexité/calculabilité.