Nicolas SCHABANEL
CNRS Researcher in Computer Science

Publications

Enseignement/Lectures:
• Usages du hasard en informatique (Using Randomness in Computer Science - Mastère MPRI)
• Cours de complexité algorithmique & optimisation discrète (Computational complexity & discrete optimisation - Mastère OJME Paris 6) [ archives video ]
• Cours d'algorithmes d'approximation (Approximation algorithms - Mastère ENS Lyon)
• Cours d'algorithmique effective (Effective algorithmics - Mastère ENS Lyon)
• Épreuve pratique d'algorithmique du concours commun des ENS (ENS entrance exam)

Vitae

Current Master and PhD Students

Grants

Organized Events

PhD Thesis

Talks

Posters

Some useful links

Research domains

• Approximation algorithms
• Randomized algorithms
• Online scheduling
• Stochastic cellular automata
• Random Structures
• Complex systems

Current and past students

• Damien Regnault, PhD advisor with Éric Thierry (since february 2005)
• Julien Robert, PhD advisor (since february 2006)
• Emmanuelle Lebhar, PhD advisor with Michel Morvan (PhD obtained in december 2005)
• Sandeep Dey, Master thesis advisor (february-july 2005)

Past organized event

• Winter School on Complex Systems

Slides of some of my talks

[ 2006 | 2005 | 2004 | 2003| 2002 | 2001 | 2000 and beyond ]

Slides of 2006

Stochastic 2D Minority: Would wearing stripes be a fatality of snob people?
CMM seminar, Santiago, Chile, Oct 2006 — Univ. de Concepción, Concepción, Chile, Nov 2006.
see paper [RST2007]

Perspectives on Small World Networks: Will artificial models explain real networks?
COST 295 Meeting, Lisbonne, Portugal, July 2006.

Machines de Turing ? Automates finis ? à pile ? Visite guidée du bestiaire informatique (in French)
Conférences d'intérêt général de l'ÉNS Lyon, Février 2006 [ vidéo (1h00) | slides ]

Customized Newspaper Broadcast: Data Broadcast with dependancies with Sandeep Dey
LATIN 2006, Valdivia, Chile, March 2006.
see Paper [DS2006]

Slides of 2005

Diffusion de journaux personnalisées (in French) with Sandeep Dey
Séminaire du LIP, École normale supérieure de Lyon, Octobre 2005.
Séminaire du LIF, Université de Aix-en-Provence-Marseille, Janvier 2006.
see Papers [DS2006]

Algorithmes d'approximation : de la théorie à la pratique (in French)
Séminaire des élève de l'école Normale Supérieure de Lyon, October 2005

Efficient decentralized routing in small worlds, with Emmanuelle Lebhar
COST 295 meeting, Krakow, sep 2005.
see Papers [LS2004] and [LS2005]

Asynchronous randomized automata: How does randomness affect decentralized computation?
with Nazim Fatès, Michel Morvan, Damien Regnault et Éric Thierry
Dagstuhl seminar, Germany, june 2005.
SciGast, Santa Fe Insitute, USA, july 2005.
see Papers [FMST2005] and [FRST2006]

Navigable graph metrics, with Philippe Duchon, Emmanuelle Lebhar and Nicolas Hanusse
COST 295 meeting, Paris, May 2005.
see Papers [DHLS2005] and [DHLS2006]

Automates cellulaires totalement asynchrones,
with Nazim Fatès, Michel Morvan, Damien Regnault et Éric Thierry
ALÉA 2005, CIRM, Mars 2005.
see Papers [FMST2005] and [FRST2006]

Slides of 2004

Routing problems in decentralized networks, with Emmanuelle Lebhar
Oberwolfach meeting on «Approximation algorithms for NP-hard problems», 6-12 june 2004.
see Papers [LS2004] and [LS2005]

Slides of 2003

L'aléatoire en algorithmique (in French)
Fête de la Science 2003, École Normale Supérieure de Lyon, October 2003

An Internet Graph Model based on trade-off optimization, with José-Ignacio Alvarez-Hamelin.
In Conference on Growing Networks and Graphs in Statistical Physics, Finance, Biology and Social Systems, Rome, 1-5 Sep. 2003. [ pdf | mov ]
see paper [AS2004]

Slides of 2002

Modeling the physical graph on the Internet
Winter School on Complex Systems, ÉNS Lyon, December 2002.

Qu'est-ce que l'algorithmique ? (in French)
Fête de la Science 2002, École Normale Supérieure de Lyon, October 2002

Un schéma d'approximation pour la dissémination de données (25 min., in French)
ROADEF 2002, Ecole Nationnale des Télécommunications de Paris, February 2002.

Quelques méthodes classiques de dérandomisation (in French)
INRIA LEMME project seminar, INRIA Sophia Antipolis, January 2002.
LIRMM Seminar, Montpellier, May 2002.
Notes complémentaires sur l'exposé.

Slides of 2001

Un schéma d'approximation pour la dissémination de données (55 min., in French)
LIFO seminar, Université d'Orléans, October 2001.

Le problème du Père-Noël (the traveling salesman problem - TSP) (in French)
Journée d'accueil des MIM 1, École Normale Supérieure de Lyon, September 2001
Related notes on TSP: DIMACS implementation challenge on TSP, D. Johnson's chapter on heuristics for symetric TSP, D. Johnson's Chapter on heuristic for Asymmetric TSP.

Simple Algorithms to Minimize Service Time in Data Broadcast Networks
DIMACS Mini-Workshop on Quality of Service Issues in the Internet, DIMACS, February 2001.
[ Pictures of the slides] [ Postscript file of the slides] [ Animated slides for recent Internet Explorer]

Slides of 2000 and beyond

Broadcasting Data on a Wireless Medium
DIMACS Mixer, ATT Labs, October 2000.
[ Pictures of the slides] [ Postscript file of the slides] [ Animated slides for recent Internet Explorer]
 
Lecture notes on Algorithmic Issues in Wireless Data Delivery
DIMACS Summer school on Foundations of Wireless Networks and Applications, DIMACS, August 2000.
(includes an up-to-date bibliography with links to the papers and authors)

Posters

It's a small world after all! (2006, in French)

Automates cellulaires asynchrones (2006, in French)

Dissémination de données (2002, in French)

Binpacking: Empaquetage automatique, un casse-tête informatique (2002, in French)
Poster de l'atelier « Empaquetage » du stand Sciences en Fête 2002 du LIP.
Conférences d'intérêt général de l'ÉNS Lyon, Novembre 2002 [ video (1h00) ]

Grants

PEPS CNRS INS2I DynaDraw (2010-2011)
Représentation statique des aspects dynamiques des graphes d'interactions (project leader)

ANR ALADDIN (2008-)
Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks

European COST 295 Dynamo (2005-)
Member of the Managment Committee, co-chair of the Smallworld Working Group with Moni Naor

CNRS Locoglobo (ATIP jeune chercheur "interactions locales: algorithmes et propriétés globales émargentes", 2005-2006)

CNRS AS Dynamo (chair of the Internet modelling working group, 2002-2003)

Some useful links...

• Websearch: Google
• Au secours des thésards : SPECIF
• Internationnal roadmap and directions (even between any address in Europe): Mapquest
• French cities maps: Mappy
• Need a phone number, an address or even a picture of an appartment in France: Les pages jaunes and Les pages blanches (very accurate)
•