• Conférence en l'honneur d'Éric Rémila pour ses 60 ans, ÉNS de Lyon, France, May 28, 2019
  (Co-organizer with Kevin Perrot) Founded by ANR, LIP and Codrin Nichitiu.
• 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

• DNA Computing: Algorithmic self-assembly, Molecular folding, Experiments (to come!)
• Algorithms: approximation, randomized, online, distributed,…
• Complex systems: such as
  • 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 supported by the “projet à risque” CalcADN (2025-2030), ANR Scalmazène (2022-2026), ANR NanoShapeLearn (2023-2027), the LIP Installation BQR (2017-18), MoPrExProgMol (2018) and AMARP (2018-20) by CNRS Mission pour l'interdisplinarité, and IXXI CalcASMol (2018-19) grants.

2024 Internship proposal: DNA computing: Theory, Models and wet lab experiments

• Octave Hazard (M2, 2021; PhD advisor 2022-2025)
• Nicolas Levy (M2, 2020; PhD advisor 2020-2023)
• Pierre Marcus (M2, 2020; 4A, 2021; PhD Advisor 2022-2024)
• Amaury Jacques (M1, 2021)
• Daria Pchelina (M1, 2019) [ Report ]
• Enka (Nikola) Blanchard (M2, 2015; PhD co-advisor with Ted Selker 2016-2019) Prix de thèse PSL SHS “Interface Sciences/Humanités” [ web | Remise du prix ]
• 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)

• M2IF CR07 Molecular programming: Theory & wet-lab experiments [ past lectures ]
• MPRI 2.11.1 Approximation Algorithms & Molecular Algorithms
• 2022 Internship proposal: DNA computing: Theory, Models and wet lab experiments

• ENSnano: a 3D DNA nanostructure design software for Windows, Mac OS and linux
  codeveloped with Nicolas Levy, 2021 [ website | youtube channel ]
• OS simulator: a fast and memory-efficient iPad app that simulates arbitrary Oritatami Systems (works with limitations on Apple silicon M1 too), 2021 [ website | download ]
• CAOS simulator: an iOS app implementing our Oritatami cellular automata simulation, 2020
  [ source code ]
• Scary Pacman: an iOS app implementing our Oritatami scaling algorihms, 2018
  [ source code ]
• Clean scan: an iOS app to take printable pictures of white, green and black board, 2015

• 2023
  • Ok: A Kinetic Model for Locally Reconfigurable Molecular Systems
    Pierre Marcus, Nicolas Schabanel and Shinnosuke Seki. In: Jonoska, N., Winfree, E. (eds) Visions of DNA Nanotechnology at 40 for the Next 40. Natural Computing Series. Springer, Singapore.
• 2022
  • Rule-of-thumb-free geometry-driven design of arbitrary complex curved DNA origami with ENSnano (Abstract)
    Nicolas Levy, Allan Mills, Gaëtan Bellot*, Nicolas Schabanel*. DNA28, New Mexico, Aug. 2022.
    
  • Turedo a new computational model for molecular nanobots?, Nicolas Schabanel.
    Invited talk at the special session «Computing with bio-molecules» at CiE 2022, Swansea, Jul 2022.
  • Oritatami systems assemble shapes no less complex than tile assembly model (aTAM)
    Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Guillaume Theyssier. STACS, 26:1-23, 2022.
    Supplementary material: [ Turedo2oritatami compiler | Full version ]
• 2021
  • ENSnano: a 3D modeling software for DNA nanostructures
    Nicolas Levy, Nicolas Schabanel. In DNA27, LIPIcs, vol. 205, pp.5:1-23, doi:10.4230/LIPIcs.DNA.27.5, 2021.
    best student paper & best presentation award.
    Download ENSnano at: [ ENSnano website ] [ Youtube channel ]
• 2020
  • Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model [ Full version ]
    Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Yuki Ubukata. In LATIN, LNCS 12118:425-436, Sao Paulo, 2020. doi:10.1007/978-3-030-61792-9_34 hal-02410874
    Download the iOS app CAOS simulator implementing our simulation [ source code ]
• 2019
  • Oritatami: A Computational Model for Molecular Co-Transcriptional Folding [ PDF & supplementary materials ]
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. IJMS (Int. J. of Molecular Sciences), Special Issue Nucleic Acid Nanotechnology, 2019, 20(9), 2259.
    https://doi.org/10.3390/ijms20092259
• 2018
  • Proving the Turing Universality of Oritatami Co-Transcriptional Folding [ Supplementary materials ]
    Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. ISAAC 2018, LIPIcs.ISAAC.2018.23:1-23:13, Jiaoxi, Yilan County, Taiwan, Dec. 2018. [ Arxiv ]
  • Know When to Fold ’Em: Self-Assembly of Shapes by Folding in Oritatami
    Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, and Hadley Thomas. DNA24, LNCS 11145:19-36, Jinan, China, Oct. 2018.
    Invited talk at UCNC2018 Self-assembly, geometry and computation workshop, Fontainebleau, June 2018.
    Download the iOS app Scary Pacman implementing our algorithms [ source code ]
• 2017
  • 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.
  • 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 Molecular 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.