Nicolas Schabanel

Premières journées du GT CoA Complexité et Algorithmes du GdR IM21-22 novembre, ESPCI, Paris 5ème--Connaissance initiale et résultats d'impossibilité en algorithmique distribuéepar David ILCINKAS (LaBRI)--Résumé (Fr). Dans le cadre de l'algorithmique distribuée, un processus ne connaît généralement pas exactement l'instance du problème lorsqu'il démarre son exécution. Ainsi de nombreux algorithmes distribuées supposent que chaque processus dispose initialement d'une certaine connaissance sur l'instance, par exemple une borne supérieure sur la taille du réseau. Pour certains problèmes, il semble que l'absence d'un certain type de connaissance initiale rende le problème impossible à résoudre. Nous nous intéresserons dans cet exposé à des formalisations possibles du concept de connaissance initiale qui permettraient de pouvoir prouver de tels résultats d'impossibilité.--Initial knowledge and impossibility results in distributed computingby David ILCINKAS (LaBRI)--Abstract (EN). In the distributed computing framework, a process does not generally know the whole instance of the problem when it starts its execution. Numerous distributed algorithms so assume that each process is initially provided with some piece of knowledge about the instance, like an upper bound on the total number of processes. For some problems, it seems that the lack of some kind of initial knowledge makes the problem impossible to solve. In this talk, we will be interested in how to formalize the concept of initial knowledge such that it would allow to formally prove such impossibility results.

MPRI 1.24 - Algorithmes Randomisés (Nicolas Schabanel, CNRS - Université Paris Diderot)[ Cours n°3 Partie B/C ]Cours n°3: Mar. Nov. 13, 2012 - 16:30-19:30 Comment débugger un programme sans rien connaître de son code ? 1) Auto-correction d'une multiplication 2) Test de linéarité, auto-correction de la linéarité, application au théorème PCPSéance d'exercices n°3: Arrondi aléatoire en programmation linéaire 1) Approximation pour Max-SAT 1.a) Instance aléatoire 1.b) Arrondi LP 1.c) Un mixte des deux 2) Arrondi aléatoire pour Min-Set-Cover

MPRI 1.24 - Algorithmes Randomisés (Nicolas Schabanel, CNRS - Université Paris Diderot)[ Cours n°2 Partie B/C ]Cours n°2: Mar. Nov. 6, 2012 - 16:00-19:00 1) Fonctions booléennes, CNF et DNF 2) L'algorithme Walk-SATSéance d'exercices n°2: Le principe de Yao & Un algorithme plus rapide pour Min-Cut 1) Mise en veille d'un disque dur 1.a) Approche déterministe 1.b) Le principe de Yao 1.c) Un algorithme randomisé optimal 2) L'algorithme de Karger-Stein (1993) pour Min-Cut

MPRI 1.24 - Algorithmes Randomisés (Nicolas Schabanel, CNRS - Université Paris Diderot)[ Cours n°1 Partie A/C ]Cours n°1: Mar. Oct 30, 2012 - 16:30-19:30 1) Introduction aux algorithmes randomisés 2) Un algorithme randomisé pour Min-CutSéance d'exercices n°1: Solutions aléatoires et dérandomisation 1) Analyse d'une partition aléatoire pour Max-Cut 2) Dérandomisation par la méthode de l'espérance conditionnelle 3) Dérandomisation par la construction d'un espace probabilisé de bits uniformes 2-à-2 indépendants 4) Généralisation à des bits uniformes k-à-k indépendants

Lecture on Approximation Algorithms at the Parisian Computer Science Masterby Nicolas Schabanel[ Lecture 3 Part B/C ]Lecture 3: Wed Oct 10, 2012 - 12:45-15:45 A Polynomial Time Randomized Approximation Scheme (PTRAS) for dense Max-Cut 1) Definition of PTAS, PTRAS, example of dependence in ε 2) Dense Max-Cut 2.a) definition 2.b) the partition of the cut covers a constant fraction of the nodes 3) A first algorithm 3.a) A non-adaptative randomized sampling based algorithm 3.b) An example on why it does not work 4) The PTRAS 4.a) Description of the algorithm 4.b) Exhaustive guessing 4.c) Hybridation 4.d) Algorithmic analysis 4.e) Probabilistic analysis 4.f) Final theorem