Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revision Both sides next revision
start [2018/01/19 10:49]
Nicolas Schabanel
start [2018/09/23 10:51]
Nicolas Schabanel [Publications]
Line 1: Line 1:
-Nicolas ​<color red>Schabanel</color>+<const> 
 +siteRoot=http://​perso.ens-lyon.fr/​nicolas.schabanel 
 +publiRoot=http://​perso.ens-lyon.fr/​nicolas.schabanel/​publications 
 +</const> 
 + 
 +<columns 100% center 440 left - > 
 +{{ :​ma_pomme.png?​440x348 |Ma pomme}}\\ 
 +{{ :​email-cnrs.png?​250x70 |Courriel}} 
 + 
 +<​newcolumn>​ 
 + 
 +==== Directeur de recherches CNRS ==== 
 +**[[http://​www.cnrs.fr/​|CNRS]] - [[http://​www.ens-lyon.fr/​LIP|LIP]]**\\  
 +**[[http://​www.ens-lyon.fr/​|École Normale Supérieure de Lyon]]**\\ 
 +46 allée d'​Italie\\ 
 +69364 Lyon Cedex 07\\ 
 +France\\ 
 +Office: **332** //(Site Monnod - Main building - 3rd floor - South)//​\\ 
 +Phone: +33 4 72 72 80 00 / +33 4 26 23 39 67 / +33 4 72 72 87 42 
 + 
 +Resident member of the\\ 
 +**[[http://​www.ixxi.fr/​|Rhône-Alpes Complex Systems Institute (IXXI)]]**\\ 
 +</​columns>​ 
 + 
 + 
 +[ [[#My current researches include|Research]] | [[http://​www.irif.fr/​gt-coa/​|GT CoA]] | [[#​Students|Students]] | [[#​Publications|Publications]] | [[#​Popularization|Popularization]] | [[#​Teaching|Teaching]] | [[#​Other|Other]] ] 
 + 
 + 
 +==== Upcoming Event  ==== 
 + 
 +==== Past Event  ==== 
 +  * **[[%%siteRoot%%/​workshop/​ComputingWithMolecularGeometry/​|Workshop:​ Computing with molecular geometry]]**,​ Villa Finaly, Florence, Italie, Nov. 20-23, 2017\\ //​(Co-organizer with Claire Lesieur and Damien Woods) Founded by [[http://​www.ixxi.fr|IXXI]],​ [[https://​tapdance.inria.fr/​|Tapdance]] and la [[http://​www.cnrs.fr/​mi/​|mission pour l'​interdisciplinarité du CNRS]]// 
 +  * **[[http://​www.irif.univ-paris-diderot.fr/​~nschaban/​GT-COA/​Journees_2017|6èmes journées]] du [[http://​www.irif.univ-paris-diderot.fr/​~nschaban/​GT-COA/​|GT CoA]]** (Complexités et Algorithmes),​ LIP, Lyon, Nov. 27-28, 2017 
 +  * **Research school on [[%%siteRoot%%/​enseignement/​2017-ER02/​|Molecular Programming:​ Theory & Wet Lab Nano-Scale Computation]]** at **[[http://​www.ens-lyon.fr/​DI/?​cat=77|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 (2017-18), MoPrExProgMol (2018) and AMARP (2018-20) by CNRS Mission pour l'​interdisplinarité,​ and IXXI CalcASMol (2018-19) 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**  
 +     * **[[%%publiRoot%%/​2018/​2018-ISAAC-OritatamiTuring-GearyMeunierSchabanelSeki.pdf|Proving the Turing Universality of Oritatami Co-Transcriptional Folding]]** [ [[http://​www.irif.fr/​~nschaban/​oritatami/​|Supplementary materials]] ]\\ Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. [[http://​isaac2018.ie.nthu.edu.tw/​|ISAAC 2018]], Jiaoxi, Yilan County, Taiwan, Dec. 2018. [ [[https://​arxiv.org/​abs/​1508.00510|Arxiv]] ] 
 +     * **[[%%publiRoot%%/​2018/​2018-DNA24-OritatamiShapes-DemaineHendricksOlsenPatitzRogersSchabanelSekiThomas.pdf|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. [[http://​dna24sdnu.com/​|DNA24]],​ Jinan, China, Oct. 2018.\\ Invited talk at [[https://​ucnc2018.lacl.fr/​self-assembly/​|UCNC2018 Self-assembly,​ geometry and computation workshop]], Fontainebleau,​ June 2018. \\ //:!: Download the iOS app [[https://​itunes.apple.com/​us/​app/​id1335581323|Scary Pacman]] implementing our algorithms [ [[https://​hub.darcs.net/​nikaoOoOoO/​OritatamiScaling|source code]] ]// 
 +  *  **2017**  
 +     * **[[%%publiRoot%%/​2017/​2017-Walcom-BlanchardSchabanel.pdf|Dynamic Facility Location: Minimizing the Sum of Radii]]**\\ Nicolas K. Blanchard, Nicolas Schabanel. //​[[http://​walcom2017.nctu.edu.tw/​index.html|WALCOM]]//,​ LNCS 10167:​30-41,​ march 2017. 
 +  * **2016** 
 +    * **[[%%publiRoot%%/​2016/​2016-Automata-Schabanel.pdf|Oritatami systems: a computational model for co-transcriptional folding]]**\\ Nicolas Schabanel. **Invited plenary talk** at //​[[http://​automata2016.ini.uzh.ch/​|Automata]]//,​ Jun. 2016.  
 +    * **[[%%publiRoot%%/​2016/​2016-MFCS-GearyMeunierSchabanelSeki.pdf|Programming biomolecules that fold greedily during transcription]]**\\ Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. //​[[http://​mfcs.ki.agh.edu.pl|MFCS]]//,​ LIPIcs 58, 43:1-43:14, Aug. 2016. 
 +    * **[[https://​arxiv.org/​abs/​1508.00510|Folding Turing is hard but feasible]]**\\ Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki.//​[[http://​highlightsofalgorithms.org/​program/​|HALG]]//,​ Jun. 2016. 
 + 
 +  *  **2015**  
 +    * **[[%%publiRoot%%/​2015/​2015-DNA21-GearyMeunierSchabanelSeki.pdf|Efficient universal computation by molecular co-transcriptional folding (Short announcement)]]**\\ Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. //​[[http://​dna21.wyss.harvard.edu/​|DNA21]]//,​ 1 page, 2015.  (Full version in submission, see above) 
 + 
 +  *  **2014** 
 +    * **[[%%publiRoot%%/​2014/​2014-ICALP-EisenstatMathieuSchabanel.pdf|Facility Location in Evolving Metrics]]**\\ with David Eisenstat and Claire Mathieu. //ICALP,// pages 459-470, 2014. 
 + 
 +  *  **2013** 
 +    * **[[%%publiRoot%%/​2013/​2013-FM-ArrighiSchabanelTheyssier.pdf|Stochastic Cellular Automata: Correlations,​ Decidability and Simulations]]**\\ with Pablo Arrighi and Guillaume Theyssier. //​Fundamenta Informaticæ,//​ 126:​121-156,​ 2013. 
 + 
 +  *  **2012** 
 +    * **[[%%publiRoot%%/​2012/​2012-JAC-ArrighiSchabanelTheyssier.pdf|Intrinsic simulations between stochastic cellular automata]]**\\ with Pablo Arrighi and Guillaume Theyssier. //AUTOMATA & JAC, EPTCS,// 90:​208–224,​ 2012. 
 +    * **[[%%publiRoot%%/​2012/​2012-PBMB-Schabanel.pdf|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** 
 +    * **[[%%publiRoot%%/​2011/​2011-Hermes-BertinBeslonGandrillonGrauwinJensenSchabanel.pdf|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. 
 +    * **[[%%publiRoot%%/​2011/​2011-STOC-GiakkoupisSchabanel.pdf|Optimal path search in small worlds: Dimension matters]]**\\ with George Giakkoupis. //STOC,// 43:​393–402,​ 2011. 
 +    * **[[%%publiRoot%%/​2011/​2011-TERANET-Schabanel.pdf|Analyzing search algorithms in smallworlds]]**\\ //TERANET// (colocated with DISC), 4 pages, Roma, Italy, Sep. 2011. 
 + 
 +  *  **2010** 
 +    * **[[%%publiRoot%%/​2010/​2010-WAOA-PruhsRobertSchabanel.pdf|Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability]]**\\ with Kirk Pruhs and Julien Robert. //WAOA,// LNCS 6534:​237–248,​ 2010. 
 +    * **[[%%publiRoot%%/​2010/​HdR-Schabanel.pdf|Systèmes complexes & algorithmes]]** (in French)\\ //​Habilitation à diriger des recherches,//​ Université Paris Diderot, 2010. [[%%publiRoot%%/​2010/​HDR-Defense-Schabanel.pdf|Slides]] 
 +    * **[[%%publiRoot%%/​2010/​2010-DMTCS-RegnaultSchabanelThierry.pdf|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** 
 +    * **[[%%publiRoot%%/​2009/​2009-TCS-Regnault-Schabanel-Thierry.pdf|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. [[http://​dx.doi.org/​10.1016/​j.tcs.2009.06.024|doi:​10.1016/​j.tcs.2009.06.024]] 
 + 
 +  *  **2008** 
 +    * **[[%%publiRoot%%/​2008/​2008-SODA-RS.pdf|Non-Clairvoyant Scheduling with Precedence Constraints]]**\\ with Julien Robert. //SODA,// 491-500, Jan. 2008. 
 +    * **[[%%publiRoot%%/​2008/​2008-LATA-RST.pdf|On the analysis of ”simple” 2D stochastic cellular automata]]**\\ with Damien Regnault and Éric Thierry. //LATA,// LNCS 5196:​452-463,​ Mar. 2008. 
 +    * **[[%%publiRoot%%/​2008/​2008-DNA14-BRS.pdf|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. 
 +    * **[[%%publiRoot%%/​2008/​2008-OPODIS-LS.pdf|Graph augmentation via metrics embedding]]**\\ with Emmanuelle Lebhar. //OPODIS,// LNCS 5401:​217-225,​ Dec. 2008. 
 + 
 +  *  **2007** 
 +    * **[[%%publiRoot%%/​2007/​2007-ESA-RS.pdf|Non-clairvoyant batch sets scheduling: Fairness is fair enough]]**\\ with Julien Robert. //ESA,// LNCS 4698:​742-753,​ Oct. 2007. 
 +    * **[[%%publiRoot%%/​2007/​2007-MFCS-RST.pdf|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. 
 +    * **[[%%publiRoot%%/​2007/​2007-MFCS-CMRS.pdf|Small alliances in graphs]]**\\ with Rodolfo Carvajal, Martín Matamala, and Iván Rapaport. //MFCS, LNCS 4708:​218-227,​ Aug. 2007.// 
 +    * **[[%%publiRoot%%/​2007/​2007-SODA-RS.pdf|Pull-Based Data Broadcast with Dependencies:​ Be Fair to Users, not to Items]]**\\ with Julien Robert. //SODA,// p. 238-247, Jan. 2007. 
 + 
 +  *  **2006** 
 +    * **[[%%publiRoot%%/​2006/​2006-DS-LATIN.pdf|Customized Newspaper Problem: Data Broadcast with dependancies]]**\\ with Sandeep Dey. //LATIN,// LNCS 3887:​362-373,​ Valdivia, march 2006. 
 +    * **[[%%publiRoot%%/​2006/​2006-FRST-LATIN2006.pdf|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. 
 +    * **[[%%publiRoot%%/​2006/​2006-TCS_special-DHLS.pdf|Could any graph be turn into a smallworld?​]]**\\ with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar. //TCS,// 355(1):​96-103,​ 2006. 
 +    * **[[%%publiRoot%%/​2006/​2006-SPAA-DHLS.pdf|Towards small world emergence]]**\\ with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar.//​SPAA,//​ 225-232, july 2006. 
 +    * **[[%%publiRoot%%/​2006/​2006-FMST-TCS.pdf|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** 
 +    * **[[%%publiRoot%%/​2005/​2005-LS-TCS.pdf|Close to optimal decentralized routing in long-range contact networks]]**\\ with Emmanuelle Lebhar. //TCS,// 348:​294–310,​ 2005. 
 +    * **[[%%publiRoot%%/​2005/​2005-DHLS-DISC.pdf|Could any graph be turn into a smallworld?​]]**\\ with Philippe Duchon, Nicolas Hanusse and, Emmanuelle Lebhar. //DISC,// LNCS 3724:​512-513,​ Cracow, september 2005. 
 +    * **[[%%publiRoot%%/​2005/​2005-FMST-MFCS.pdf|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** 
 +    * **[[%%publiRoot%%/​2004/​2004-LS-ICALP2004.pdf|Almost optimal decentralized routing in long-range contact networks]]**\\ with Emmanuelle Lebhar. //ICALP,// Turku, Finland, july 2004. [[%%publiRoot%%/​2004/​2004-LS-ICALP2004-FULL.pdf|Full]] 
 +    * **[[%%publiRoot%%/​2004/​2004-AS-EPJB.pdf|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** 
 +    * **[[%%publiRoot%%/​2003/​KS03.pdf|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** 
 +    * **[[%%publiRoot%%/​2000/​Schabanel-PhDThesis.ps.gz|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) [[%%publiRoot%%/​2000/​Schabanel-PhDThesis.pdf|PDF]]\\ //PhD Thesis,// École normale supérieure de Lyon, 2000. Advisors: Claire Kenyon and Stéphane Ubéda (local advisor). 
 +    * **[[%%publiRoot%%/​2000/​KSY2000.pdf|Polynomial-Time Approximation Scheme for Data Broadcast]]**\\ with Claire Kenyon and Neal E.  Young. //STOC,// pages 659-666, May 2000. 
 +    * **[[%%publiRoot%%/​2000/​S00.pdf|The databroadcast problem with preemption]]**\\ //STACS,// LNCS 1770:​181-192,​ Lille, February 2000.  [[%%publiRoot%%/​1999/​S99-RR1999-49.ps.gz|Full]] 
 + 
 +  *  **1999** 
 +    * **[[%%publiRoot%%/​1999/​KS99.pdf|The data broadcast problem with non-uniform transmission times]]**\\ with Claire Kenyon. //SODA,// pp.547–556. SIAM, Jan. 1999. 
 +    * **[[%%publiRoot%%/​1999/​FS99.ps.gz|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** 
 +    * **[[%%publiRoot%%/​1998/​SUZ98.ps.gz|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. 
 +    * **[[%%publiRoot%%/​1997/​BGMS97-RR1997-13.ps.gz|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. [[%%publiRoot%%/​1998/​BGMS98-RR1998-18.ps.gz|Full]]  
 +    * **[[%%publiRoot%%/​1996/​ALST96.ps.gz|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 
 +     * **[[%%publiRoot%%/​2016/​2016-Tangente-Schabanel1.pdf|Vérifier une preuve en n'en lisant que quelques lettres !]]**\\ Nicolas Schabanel. //​[[http://​www.poleditions.com/​pole/​publications.php?​collection=Tangente%20HS%20kiosque|Tangente]]//,​ Hors série n°55:​144-147 Les démonstrations,​ Jan. 2016 
 +    * **[[%%publiRoot%%/​2016/​2016-Tangente-Schabanel1.pdf|Le «petit» théorème PCP]]**\\ Nicolas Schabanel. //​[[http://​www.poleditions.com/​pole/​publications.php?​collection=Tangente%20HS%20kiosque|Tangente]]//,​ Hors série n°55:​148-151 Les démonstrations,​ Jan. 2016 
 +    * **[[%%publiRoot%%/​2016/​2016-Tangente-Schabanel1.pdf|Réduire la taille d'une preuve]]**\\ Nicolas Schabanel. //​[[http://​www.poleditions.com/​pole/​publications.php?​collection=Tangente%20HS%20kiosque|Tangente]]//,​ Hors série n°55:​152-155 Les démonstrations,​ Jan. 2016 
 +  * 2015 
 +    * **[[http://​www.societe-informatique-de-france.fr/​wp-content/​uploads/​2015/​03/​1024-hs1-guion-schabanel.pdf|La médiation en informatique vue par le CNRS]]**\\ with Laure Guion. //1024// (Bulletin de la Société Informatique de France), //​[[http://​www.societe-informatique-de-france.fr/​bulletin/​1024-numero-hs1/​|Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public »]],// p.19-21, février 2015. 
 +    * **[[http://​www.societe-informatique-de-france.fr/​wp-content/​uploads/​2015/​03/​1024-hs1-schabanel.pdf|Les hottes du Père Noël]]**\\ //1024// (Bulletin de la Société Informatique de France), //​[[http://​www.societe-informatique-de-france.fr/​bulletin/​1024-numero-hs1/​|Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public »]],// p.79-82, février 2015. 
 + 
 +  * 2013 
 +    * **[[%%publiRoot%%/​2012/​2012-Maths-Pansu-Schabanel.pdf|Couper,​ attendrir, trancher, réduire : un conte culinaire sur la résolution informatique des problèmes difficiles.]]** (in French)\\ With Pierre Pansu. //​[[http://​smf.emath.fr/​content/​lexplosion-continue-sommaire|Mathématiques,​ l’explosion continue]],//​ pages 15-22, 2013. 
 + 
 +  * 2007 
 +    * **[[http://​interstices.info/​jcms/​c_15920/​routage-dans-les-petits-mondes?​qs=id%3Djalios_5127|Routage dans les petits mondes]] ​ [[%%publiRoot%%/​2007/​2007-Interstices-LS.pdf|PDF]]**\\ with Emmanuelle Lebhar. //)i( interstices//​ INRIA popularization website, 2007. 
 + 
 +  * 2003 
 +    * **[[%%publiRoot%%/​2003/​2003.04-Minotaure-Schabanel.pdf|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 [[https://​wikimpri.dptinfo.ens-cachan.fr/​doku.php?​id=cours:​c-2-11-1|Approximation Algorithms & Molecular Algorithms]]** 
 +