Nicolas SCHABANEL's Vitae

Topics: [ General informations l Cursus | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]

General informations

Topics: [ General informations l Cursus | Current and past students | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]

Cursus

Topics: [ General informations l Students | Cursus | Publications | Teaching Experience | Popularization (vulgarisation) | Research Administration | Collaborations | Homepage ]

Current and past students

Julien Robert, PhD advisor (PhD obtained in Dec. 2009)

Damien Regnault, PhD co-advisor with Éric Thierry (PhD obtained in Dec. 2008)

Emmanuelle Lebhar, PhD co-advisor with Michel Morvan (PhD obtained in december 2005 - now CNRS Researcher)

Sandeep Dey, Master thesis advisor (february-july 2005)

Publications

[ 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2000 | 1999 | 1998 and beyond ]

2010

Minimizing maximum flowtime with arbitrary speedup curves and precedence constraints, with Kirk Pruhs and Julien Robert. En cours de rédaction (2010).

Fabriquer du hasard avec des conjectures d'informatique théorique, Exposé invité aux journées ALÉA 2010, CIRM, Mar. 2010.

Open problem session - Non-clairvoyant with precedence constraints: Towards a measure of the worst case degree of parallelism within a precedence constraints DAG structure, Invitation to the Dagstuhl seminar n°10071 « Scheduling » (organized by Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring & Kirk Pruhs), Feb. 2010.

2009

Complex Systems from a computer scientist point of view
Invited conference at 3rd colloque national "Vers une science et ingénierie des systèmes complexes" (SISC2009), Auditorium du CNRS, Paris, Nov. 2009.

Systèmes complexes & Algorithmes, Habilitation à diriger des recherches, 254 pages, 2009.

Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority, with Damien Regnault and Éric Thierry.
Theoretical Computer Science (2009), doi:10.1016/j.tcs.2009.06.024

2008

On stochastic cellular automata [ .key.zip ]
Invited conference at Philippe Flajolet's 60th birthday, École normale supérieure, Paris, Dec. 2008.

Encuentra el infinito : Escher y la geometría imposible
Invited conference at the opening of the exhibition Encuentra el infinito at the museum of science, el museo interactivo mirador, Santiago de Chile, Sep. 2008.

Non-Clairvoyant Scheduling with Precedence Constraints, with Julien Robert.
In Proc. of the 19th ACM/SIAM Symp. on Discrete Algorithms (SODA), pp. 491-500, Jan. 2008.

On the analysis of ”simple” 2D stochastic cellular automata, with Damien Regnault and Éric Thierry. In LNCS Proc. of 2nd Int. Conf. on Language and Automata Theory and Applications (LATA), 5196:452-463, Mar. 2008.

Time optimal self-assembling of 2D and 3D shapes: the case of squares and cubes, with Florent Becker and Éric Rémila. In LNCS Proc. of 14th Int. Meeting on DNA Computing (DNA14), to appear, June 2008.

Graph augmentation via metrics embeddings, with Emmanuelle Lebhar. In LNCS Proc. of 12th Int. Conf. on Principles of Distributed Systems (OPODIS), 5401:217-225, Dec. 2008.

2007

Non-clairvoyant batch set scheduling: Fairness is fair enough, with Julien Robert.
In Proc. of 15th European Symposium on Algorithms (ESA), LNCS 4698, pp. 742-753, Oct. 2007.

Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority, with Damien Regnault and Éric Thierry.
In Proc. of 32nd Conf. on Mathematical Foundation of Computer Science (MFCS), LNCS 4708, pp. 320-332, Aug. 2007. [ Journal version (TCS 2009) ]

Small alliances in graphs, with Rodolfo Carvajal, Martín Matamala, and Iván Rapaport.
in Proc. of 32nd Conf. on Mathematical Foundation of Computer Science (MFCS), LNCS 4708, pp. 218-227, Aug. 2007.

Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to Items, with Julien Robert.
In Proc. of the 18th ACM/SIAM Symp. on Discrete Algorithms (SODA), p. 238-247, Jan. 2007.

Routage dans les petits mondes, with Emmanuelle Lebhar. [ .pdf ]
In )i( interstices INRIA popularization website, 2007.

2006

Customized Newspaper Problem: Data Broadcast with dependancies, with Sandeep Dey.
In Proc. of the 7th Latin American Theoretical INformatics conference (LATIN 2006), LNCS 3887:362-373, Valdivia, march 2006.

Asynchronous behavior of double-quiescent elementary cellular automata, with Nazim Fatès,
Damien Regnault and Éric Thierry.
In Proc. of the 7th Latin American Theoretical INformatics conference (LATIN 2006), LNCS 3887:455-466, Valdivia, march 2006.

Could any graph be turn into a smallworld?
with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar.
In TCS special edition on complex networks, 355(1):96-103, 2006.

Towards small world emergence, with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar.
In Proc. of ACM Symp. on Parallel Algorithms and Architectures (SPAA), 225-232, july 2006.

Fully asynchronous behavior of double-quiescent elementary cellular automata,
with Nazim Fate`s, Michel Morvan, Éric Thierry.
In Theoretical Computer Science, 362(1-3):1-16, 2006

2005

Asynchronous randomized automata: how does randomness affect decentralized algorithms execution?
Invited conference at the Dagstuhl seminar 05201 « Approximation and randomized
algorithms », June 2005.

Close to optimal decentralized routing in long-range contact networks, with Emmanuelle Lebhar.
Invited publication in TCS special series on ICALP 2004, 348:294–310, 2005.

Could any graph be turn into a smallworld?
with Philippe Duchon, Nicolas Hanusse and, Emmanuelle Lebhar.
In LNCS Proc. of the 19th Distributed Computing International Conference (DISC2005), 3724:512-513, Cracow, september 2005.

Fully asynchronous behavior of double-quiescent elementary cellular automata, with Nazim Fatès, Michel Morvan and Éric Thierry.
In LNCS Proc. of the 30th Mathematical Foundations of Computer Science sympsosium (MFCS2005), 3618:316-327, Gdansk, september 2005.

2004

Routing problems in decentralized networks
Invited conference at Oberwolfach seminar « Approximation algorithms for NP-hard problems », June 2004.

Almost optimal decentralized routing in long-range contact networks, with Emmanuelle Lebhar.
In Proc. of the 31st Internation 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Turku, Finland, july 2004.

An Internet Graph Model based on trade-off optimization, with José-Ignacio Alvarez-Hamelin.
In European Physical Journal B (EPJB), 38(2):231-238, 2004.
A preliminary version of the paper was presented at the Conference on Growing Networks and Graphs in Statistical Physics, Finance, Biology and Social Systems, Rome, 1-5 Sep. 2003.
Also Optimisation et modélisation du graphe des systèmes autonomes d'Internet (AS graph)
In in Proc. of Algotel 2003, May 2003.

2003

The data broadcast problem with non-uniform transmission times, with Claire Kenyon.
In Algorithmica (2003) 35:146-175, February 2003.
A preliminary version of this paper was published in Proc. of the 10th ACM-SIAM Symp. on Discrete Algorithms (SODA 1999), pages 547-556. ACM-SIAM, January 1999.

Optimisation et modélisation du graphe des systèmes autonomes d’Internet (AS graph),
with J. I. Alvarez Hamelin. In Actes d’Algotel 2003, pp. 75–82, Banyuls, mai 2003.

Thèse idiote: le hasard fabrique des certitudes (in French)
In Le minotaure (trimenstrial journal, 20 000ex), 1:66-69, april-june 2003.

2000

Polynomial-Time Approximation Scheme for Data Broadcast, with Claire Kenyon and Neal E. Young. [ .pdf ]
In Proc. of the 32nd ACM Symposium on Theory of Computing (STOC 2000), pages 659-666, May 2000.
Currently working on the full version of the paper.

The databroadcast problem with preemption
In LNCS 1770 Proc. of the 17th International Symposium on Theoritical Aspects of Computer Science (STACS 2000), page 181-192, Lille, February 2000.
Currently working on the full version of the paper.

A state of the art in Data Dissemination
Invited conference to the international seminar « Linear, semidefinite programming and randomization methods for combinatorials optimization problems » at Dagstuhl, January 2000.

1999

The data broadcast problem with non-uniform transmission times, with Claire Kenyon.
In Proc. of the 10th ACM-SIAM Symp. on Discrete Algorithms SODA’99, pages 547–556. SIAM, Jan. 1999.

A randomized BSP algorithm for the maximal independent set problem, with Afonso Ferreira.
In Parallel Processing Letters, Vol. 9 No. 3, pages 411-422, 1999.
A preliminary version was published in Proc. of the 4th Int. Symp. on Parallel Architectures, Algorithms, and Networks (I-SPAN'99) , pages 284-289, Juin 1999.

A note on upper bounds for the span of the frequency planning in cellular networks, with Stéphane Ubéda and Janez Zerovnik.
Preprint, 1999.

1998 and beyond

Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionnaries, with Luc Bougé, J. Gabarro, and X. Messeguer
LIP Research Report RR98-18, LIP, March 1998. Full version of the paper below.

Concurrent rebalancing of AVL trees: a fine-grained approach, with  Luc Bougé, J. Gabarro, and X. Messeguer.
In LNCS Europar'97, volume 1300, pages 421-429, Août 1997.

Basic linear algebra operations in SLI arithmetic, with M. A. Anuta, D. W. Lozier, and Peter R. Turner.
In LNCS Europar'96, volume 1124, pages 193-202, Août 1996.

PhD Thesis

English title: « Approximation algorithms for wireless networks: Scheduling data dissemination and Static frequency assignment »

Advisors: Claire Kenyon & Stéphane Ubéda (local advisor)

abstract & downloads

Topics: [ General informations l Cursus | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]

Teaching Experience

• 2010-2011: 24h lectures (+8h training classes) on Using Randomness in Computer Sciences at the MPRI Master
   
• 2009-2010: 2x3x2h lectures at the complex systems master M2 of the ÉNS Lyon, Dec. 2009 - Mar. 2010:
  • Intervention de 3x2h dans le cours « Problèmes de satisfaction de contraintes » (Responsable du cours, 2 autres intervenants: Marc Mézard (physicien, Orsay) & Laurent Simon (LRI, Orsay)).
  • Intervention de 3x2h: « Auto-assemblage algorithmique d'objets nanoscopiques » dans le cours «  Organisation spatiale et temporelle en matière condensée » (Responsable: Jean-Louis Barrat, physicien à l'univ. Claude Bernard (Lyon I))
  
  
• 2009: 3h lectures at the master M2 bioinformatique et modélisation of the INSA de Lyon, Dec. 2009 - « Computer sciences & Complex Systems ».
   
• 2009: 2 x 3h lectures at the Complex Systems Summer School (IXXI - ENS LYON), July 2009 - « Complex Systems from a computer scientist point of view » [ Videos available on youtube ]
   
• 2009: 2h00 de cours « Introduction à l'algorithmique en-ligne non-clairvoyante : vers une algorithmique immédiatement utile » lors de la semaine sport-étude des étudiants de licence 3 en informatique de l'École normale supérieure de Lyon, 22 janvier 2009 [ slides | .key | vidéos 1 2 ]
   
• 2008: 18h00 (6 x 3h) de cours « introduction à la complexité algorithmique, NP-complétude et optimisation discrète » correspondant à la seconde partie du cours d'A. Bondy « Optimisation discrète » au sein du mastère M2 Mathématiques et Applications de l'université Pierre et Marie Curie (Paris 6), spécialité Mathématiques de la modélisation, parcours Optimisation, Théorie de Jeux, Modélisation en Économie (OJME). J'ai filmé les cours qui sont disponibles gratuitement sur le web. [ vidéos ]
   
• 2008: Invited Lecture at the International Summer School on Discrete Mathematics « Aplicaciones del azar a los algoritmos: de la aceleración a la auto-corrección» (5 x 1h15; 3h to 4th year - computer science PhD Students and Academics), Instituto de Systemas Complejos de Valparaíso (ISCV), Valparaíso, jan. 2008.
   
• 2007: Invited Lecture at the International Summer School on Complex Systems « On the use of Randomness in Computer Science and Computer Systems » (3 x 1h; 3h to 4th year - PhD Students from various fields (biology, physics,...)), Instituto de Systemas Complejos de Valparaíso (ISCV), Valparaíso, jan. 2007.
   
• 2007: Teacher of a 30h lecture (20h lecture + 10h pratice) on algoritmos de aproximación to fourth year university at Universidad de Chile. Teaching assistant: Julien Robert.
   
• 2004-2006: Teacher of a 64h lecture (32h lecture + 32h pratice) on Efficient algorithms to third and fourth year university at Magistère d'Informatique et Modélisation of ÉNS Lyon. Teaching assistant: none (2004-2005), Sylvain Périfel (2005-2006).
  Our team ranked 1st in South-west europe in 2004 and took part to the finals in Shanghai in 2005 (ICPC)!
   
• 2003-2005: Teacher of a 64h lecture (32h lecture + 32h pratice) on Approximation algorithms to fourth year university at Magistère d'Informatique et Modélisation of ÉNS Lyon. Teaching assistant: Emmanuelle Lebhar (2003), Guillaume Theyssier (2004), Laurent Lyaudet (2005).
   
• 2003, 2004, 2005: Local organizer of the programming and algorithmic contest for the competitive entrance to the écoles normales supérieures (including conception and correction of a 3 over 9 of the exams) and re-conception of the contest (2005). see EPAP.
   
• 1997-1998/1999-2000: Teaching assistant in courses addressed to first to fourth year university at Magistère d'Informatique et Modélisation of ÉNS Lyon and at the Université Claude Bernard, Lyon I:
  • Calculability and Rewriting
  • Functional programming
  • Object Oriented Languages and Software Engineering
  • Automata and Formal Languages
     
• Summer 1999: Supply Professor J. Aslam, (3 courses and 3 extra-hours) teacher of the undergraduate algorithm course CS25 at Dartmouth College, New Hampshire, USA. I presented the chapters:
  • End of "Greedy Algorithms",
  • The complete lecture on "Amortized Analysis".
     
• 1994-1996: Teaching « Initiation to computer science and programing » to first year university at the lycée du Parc.

Popularization (vulgarisation)

• 2009: Workshop « Fenêtre sur l'infini » where the visitors could meet the infinity à la Escher in real time and have their pictures taken next to a frame transformed à la Escher to the infinity and beyond, Science en fête 2009, Université Paris Diderot. (next year we'll do it with a better webcam)
   
  Followed by a conference: Fenêtre sur l'infini: Escher et la géométrie impossible (in French)
   
• 2006-2008: collaboration with the museum of Science of Santiago de Chile, el Museo Interactivo Mirador. Contract signed with them to build a permanent exhibtion on realtime escher-like transformation with webcam, camera and pictures to be taken back home, unveiled in september 2008 [ link ]
   
• 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 ]
   
• October 2003: « Science week » at the ÉNS Lyon
  • 30 min talk : « Randomness in Computer Science ». [ video ]
  • Workshop on « Binpacking » run during 3 days (with help of a graduate student). [ poster | video ]
     
• Thèse idiote: le hasard fabrique des certitudes
  In Le minotaure (trimenstrial journal, 20 000ex), 1:66-69, april-june 2003.
   
• 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) ]
     
• 2002-2003: Teaching « Initiation to computer science and programing » to second year university at the lycée du Parc.
   
• October 2002: « Science week » at the ÉNS Lyon
  • 30 min talk : « What is an algorithm ?». [ slides ]
  • Workshop on « Binpacking » run during 3 days (with help of a mim student). [ poster | video ]
     
• October 1999: « Science week » at the ÉNS Lyon (a week which is nation-wide dedicated to presentations of today's research in French universities to the public) :
  • 45 min talk: « The discovery of undecidability in mathematics and computer science, or how one can prove by counting that unsolvable problems exist ».
   

Topics: [ General informations l Cursus | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]

Research Administration & Grants

Topics: [ General informations l Cursus | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]

Collaborations

Here is a list of people I worked with:

• Kirk Pruhs (Pittsburgh Univ.) see [KRS10]
• Florent Becker (LIP, ÉNS Lyon) see [BRS08]
• Éric Rémila (LIP, ÉNS Lyon) see [BRS08]
• Iván Rapaport (CMM-DIM, Universidad de Chile, Chili) see [CMRS2007]
• Martín Matamala (CMM-DIM, Universidad de Chile, Chili) see [CMRS2007]
• Rodolfo Carvajal (CMM-DIM, Universidad de Chile, Chili) see [CMRS2007]
• Luz Lindergaard (Director of the Museo interactivo mirador, Santiago de Chile) see [Infinito]
• Karol Suchan (Universidad Adolfo Ibañez, Chili) see [Infinito]
• Philippe Duchon (Labri, université de Bordeaux, France) see [DHLS2005] [DHLS2006]
• Nicolas Hanusse (Labri, université de Bordeaux, France), see [DHLS2005] [DHLS2006]
• Neal E. Young (during a 4 months stay at Dartmouth College, New Hampshire, USA, 1998-99), see [KSY00]
• Janez Zerovnik (several visits, 1998) see [SUZ98]
• Peter R. Turner (during a 3 months stay at US Naval Academy, Maryland, USA, 1995), see [ALST96]
• Lata Narayanan (short visit at Concordia University, Montréal, Canada, 1998), improvement in [SUZ99]
• Afonso Ferreira (LIP, ÉNS Lyon, France, 1999), see [FS99]
• José Ignacio Alvarez-Hamelin (LRI, France, 2003), see [AS03]
• And of course: Emmanuelle Lebhar, Damien Regnault, Julien Robert, Sandeep Dey, Éric Thierry, Claire Kenyon, Stéphane Ubéda, and Luc Bougé.

Topics: [ General informations l Cursus | Publications | Teaching Experience | Research Administration | Collaborations | Homepage ]