Nicolas Schabanel Directeur de recherches CNRS Laboratoire d'informatique algorithmique : Fondements et applications (LIAFA) Université Paris Diderot Bât. Sophie Germain, 8 Place FM/13, 4th floor, 75013 Paris, France Office: A6 (1st floor) Resident member of the Rhone-Alpes Complex Systems Institute (IXXI) École normale supérieure de Lyon 5 Rue du Vercors, 69007 Lyon, France Office: 4005 (4th floor) [ Research | Students | Publications | Talks | Teaching | Other ]

My current researches include

• Algorithms: approximation, randomized, online, distributed,...
• Complex systems: such as
  • Small world phenomenon: analysis, algorithms design, modelization,...
  • Stochastic cellular automata: definition, analysis, intrinsic simulations, local probabilistic correlations,...
  • Complex networks: clustering and drawing of dynamical networks
• Algorithmic self-assembly
• Random systems

Students

• Damien Regnault (PhD co-advisor with Éric Thierry, 2005-2008)
• Julien Robert (PhD advisor, 2006-2009)
• Emmanuelle Lebhar (PhD co-advisor with Michel Morvan, 2003-2005)
• Sandeep Dey (Master thesis advisor, 2005)

Publications

• 2013
  • Stochastic Cellular Automata: Correlations, Decidability and Simulations
    with Pablo Arrighi and Guillaume Theyssier. Fundamenta Informaticæ, 126:1-36, 2013.
• 2012
  • Intrinsic simulations between stochastic cellular automata
    with Pablo Arrighi and Guillaume Theyssier. AUTOMATA & JAC, EPTCS 90:208–224, 2012.
  • Randomness + Determinism = Progresses: Why random processes could be favored by evolution
    Progress in Biophysics and Moleculer Biology (Special edition on the conference ”Chance at the heart of the cell”), 110(1):129–136, 2012.
  • Couper, attendrir, trancher, réduire : un conte culinaire sur la résolution informatique des problèmes difficiles. (in French)
    With Pierre Pansu. L’explosition des mathématiques, page 6 pages, 2012. À paraître.
• 2011
  • Les complexités : point de vue d’un institut des systèmes complexes (in French)
    with Éric Bertin, Guillaume Beslon, Olivier Gandrillon, Sébastian Grauwin, and Pablo Jensen. Hermès, 60:145–150, 2011.
  • Optimal path search in small worlds: Dimension matters
    with George Giakkoupis. STOC, 43:393–402, 2011.
  • Analyzing search algorithms in smallworlds
    TERANET (colocated with DISC), 4 pages, Roma, Italy, Sep. 2011.
• 2010
  • Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability
    with Kirk Pruhs and Julien Robert. WAOA, LNCS 6534:237–248, 2010.
  • Systèmes complexes & algorithmes (in French)
    Habilitation à diriger des recherches, Université Paris Diderot, 2010. [ Slides ]
  • On the analysis of “simple” 2D stochastic cellular automata
    with Damien Regnault and Éric Thierry. Invited publication to the special issue of DMTCS in honor of Philippe Flajolet, 12(2):263–294, 2009.
• 2009
  • Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority
    with Damien Regnault and Éric Thierry. TCS (2009), doi:10.1016/j.tcs.2009.06.024
• 2008
  • Non-Clairvoyant Scheduling with Precedence Constraints
    with Julien Robert. SODA, 491-500, Jan. 2008.
  • On the analysis of ”simple” 2D stochastic cellular automata
    with Damien Regnault and Éric Thierry. LATA, LNCS 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. DNA14, LNCS 5347:144–155, June 2008.
  • Graph augmentation via metrics embedding
    with Emmanuelle Lebhar. OPODIS, LNCS 5401:217-225, Dec. 2008.
• 2007
  • Non-clairvoyant batch sets scheduling: Fairness is fair enough
    with Julien Robert. ESA, LNCS 4698: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. MFCS, LNCS 4708:320-332, Aug. 2007.
  • Small alliances in graphs
    with Rodolfo Carvajal, Martín Matamala, and Iván Rapaport. MFCS, LNCS 4708:218-227, Aug. 2007.
  • Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to Items
    with Julien Robert. SODA, p. 238-247, Jan. 2007.
  • Routage dans les petits mondes [ PDF ]
    with Emmanuelle Lebhar. )i( interstices INRIA popularization website, 2007.
• 2006
  • Customized Newspaper Problem: Data Broadcast with dependancies
    with Sandeep Dey. LATIN, LNCS 3887:362-373, Valdivia, march 2006.
  • Asynchronous behavior of double-quiescent elementary cellular automata
    with Nazim Fatès, Damien Regnault and Éric Thierry. LATIN, LNCS 3887:455-466, Valdivia, march 2006.
  • Could any graph be turn into a smallworld?
    with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar. TCS, 355(1):96-103, 2006.
  • Towards small world emergence
    with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar. SPAA, 225-232, july 2006.
  • Fully asynchronous behavior of double-quiescent elementary cellular automata
    with Nazim Fatès, Michel Morvan, Éric Thierry. TCS, 362(1-3):1-16, 2006
• 2005
  • Close to optimal decentralized routing in long-range contact networks
    with Emmanuelle Lebhar. TCS, 348:294–310, 2005.
  • Could any graph be turn into a smallworld?
    with Philippe Duchon, Nicolas Hanusse and, Emmanuelle Lebhar. DISC, LNCS 3724:512-513, Cracow, september 2005.
  • Fully asynchronous behavior of double-quiescent elementary cellular automata
    with Nazim Fatès, Michel Morvan and Éric Thierry. MFCS, LNCS 3618:316-327, Gdansk, september 2005.
• 2004
  • Almost optimal decentralized routing in long-range contact networks
    with Emmanuelle Lebhar. ICALP, Turku, Finland, july 2004. [ Full ]
  • An Internet Graph Model based on trade-off optimization
    with José-Ignacio Alvarez-Hamelin. 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.
• 2003
  • The data broadcast problem with non-uniform transmission times
    with Claire Kenyon. Algorithmica, 35:146-175, February 2003.
    A preliminary version of this paper was published in SODA 1999, pages 547-556.
  • Thèse idiote: le hasard fabrique des certitudes (in French)
    Le minotaure (trimenstrial journal, 20 000ex), 1:66-69, april-june 2003.
• 2000
  • Algorithmes d'approximation pour les télécommunications sans fil : Ordonnancement pour la dissémination de données et Allocation statique de fréquences (in French) [ PDF ]
    PhD Thesis, École normale supérieure de Lyon, 2000.
    Advisors: Claire Kenyon and Stéphane Ubéda (local advisor)
  • Polynomial-Time Approximation Scheme for Data Broadcast
    with Claire Kenyon and Neal E. Young. STOC, pages 659-666, May 2000.
  • The databroadcast problem with preemption
    STACS, LNCS 1770:181-192, Lille, February 2000. [ Full ]
• 1999
  • The data broadcast problem with non-uniform transmission times
    with Claire Kenyon. SODA, pp.547–556. SIAM, Jan. 1999.
  • A randomized BSP algorithm for the maximal independent set problem
    with Afonso Ferreira. PPL, 9(3):411-422, 1999.
    A preliminary version was published in I-SPAN'99, pages 284-289, june 1999.
• 1998 and beyond
  • Parallel algorithm for the optimization of the span of an hexagonal frequency planning graph
    with Stéphane Ubéda and Janez Žerovnik. Telepar, pages 237-241, Boston, Avril 1998. SCS.
  • Concurrent rebalancing of AVL trees: a fine-grained approach
    with Luc Bougé, J. Gabarro, and X. Messeguer. Euro-Par, LNCS 1300:421-429, Août 1997. [ Full ]
  • Basic linear algebra operations in SLI arithmetic
    with M. A. Anuta, D. W. Lozier, and Peter R. Turner. Euro-Par, LNCS 1124:193-202, Août 1996.

Talks

Teaching

Other

• Algoseum: “Bringing scientific interactive games and exhibitions to science museum”