• Workshop: Computing with molecular geometry, Villa Finaly, Florence, Italie, Nov. 20-23, 2017
  (Co-organizer with Claire Lesieur and Damien Woods) Founded by IXXI, Tapdance and la mission pour l'interdisciplinarité du CNRS
• 6èmes journées du GT CoA (Complexités et Algorithmes), LIP, Lyon, Nov. 27-28, 2017

• Research school on Molecular Programming: Theory & Wet Lab Nano-Scale Computation at ENS Lyon, Jan 16-20, 2017
  Free to register and open to everyone

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

My work is currently supported by the ANR-2010-BLAN-0204 MAGNUM, ANR-12-BS02-005 RDAM and IXXI-MOLECAL grants.

• Nicolas Blanchard (M2, 2015; PhD advisor 2016-)
• Alberto Vera Azócar (U. Chile, several research internships 2013, 2015)
• 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)

• 2017
  • Proving the Turing Universality of Oritatami Co-Transcriptional Folding
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. Submitted, 65 pages, july 2017. [ Supplementary materials ]
  • Dynamic Facility Location: Minimizing the Sum of Radii
    Nicolas K. Blanchard, Nicolas Schabanel. WALCOM, LNCS 10167:30-41, march 2017.
• 2016
  • Oritatami systems: a computational model for co-transcriptional folding
    Nicolas Schabanel. Invited plenary talk at Automata, Jun. 2016.
  • Programming biomolecules that fold greedily during transcription
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. MFCS, LIPIcs 58, 43:1-43:14, Aug. 2016.
  • Folding Turing is hard but feasible
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki.HALG, Jun. 2016.

• 2015
  • Efficient universal computation by molecular co-transcriptional folding (Short announcement)
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. DNA21, 1 page, 2015. (Full version in submission, see above)

• 2014
  • Facility Location in Evolving Metrics
    with David Eisenstat and Claire Mathieu. ICALP, pages 459-470, 2014.

• 2013
  • Stochastic Cellular Automata: Correlations, Decidability and Simulations
    with Pablo Arrighi and Guillaume Theyssier. Fundamenta Informaticæ, 126:121-156, 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.

• 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, 410(47-49):4844-4855S, 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.

• 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.

• 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. In 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.

• 2016
  • Vérifier une preuve en n'en lisant que quelques lettres !
    Nicolas Schabanel. Tangente, Hors série n°55:144-147 Les démonstrations, Jan. 2016
  • Le «petit» théorème PCP
    Nicolas Schabanel. Tangente, Hors série n°55:148-151 Les démonstrations, Jan. 2016
  • Réduire la taille d'une preuve
    Nicolas Schabanel. Tangente, Hors série n°55:152-155 Les démonstrations, Jan. 2016
• 2015
  • La médiation en informatique vue par le CNRS
    with Laure Guion. 1024 (Bulletin de la Société Informatique de France), Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public », p.19-21, février 2015.
  • Les hottes du Père Noël
    1024 (Bulletin de la Société Informatique de France), Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public », p.79-82, février 2015.

• 2013
  • Couper, attendrir, trancher, réduire : un conte culinaire sur la résolution informatique des problèmes difficiles. (in French)
    With Pierre Pansu. Mathématiques, l’explosion continue, pages 15-22, 2013.

• 2007
  • Routage dans les petits mondes PDF
    with Emmanuelle Lebhar. )i( interstices INRIA popularization website, 2007.

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

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