This is an old revision of the document!
Directeur de recherches CNRS
CNRS - LIP
Resident member of the |
[ Research | GT CoA | Students | Publications | Popularization | Teaching | Other ]
Upcoming Event
Past Event
- 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
My current researches include
- 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 currently supported by the LIP Installation BQR and MOPREXPROGMOL CNRS MI grants.
Students
- 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)
Publications
- 2018
- Proving the Turing Universality of Oritatami Co-Transcriptional Folding [ Supplementary materials ]
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. ISAAC 2018, Jiaoxi, Yilan County, Taiwan, Dec. 2018. - 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, Jinan, China, Oct. 2018.
Invited talk at UCNC2018 Self-assembly, geometry and computation workshop, Fontainebleau, June 2018.
- 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 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. http://perso.ens-lyon.fr/nicolas.schabanel/publications/2010/HDR-Defense-Schabanel.pdf|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.
- 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.
Popularization
- 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.
Teaching
- MPRI 2.11.1 Approximation Algorithms & Molecular Algorithms
Other
- Algoseum: “Bringing scientific interactive games and exhibitions to science museum”