• Home

Arnaud de Mesmay

I am a CNRS researcher, working in Laboratoire d'Informatique Gaspard Monge, close to Paris. I recently moved from Gipsa-lab in Grenoble. Before that, I spent one year as a post-doc at IST Austria, working in the group of Uli Wagner. And before that, I did my PhD studies at the Ecole Normale Superieure in Paris, under the supervision of Éric Colin de Verdiere.

I have a broad interest in the interfaces between mathematics, in particular geometry and topology of low-dimensional spaces, and theoretical computer science. On this page you can find a (slightly outdated) CV, and some of my works. You can contact me by sending an email to ademesmay (at) gmail (dot) com

Papers

• Voting algorithms for unique games on complete graphs, arxiv.
  with Antoine Méot, Moritz Mühlenthaler and Alantha Newman.
• Distributed coloring and the local structure of unit-disk graphs, arxiv.
  with Louis Esperet and Sébastien Julliot.
  ALGOSENSORS 2021
• Hard Diagrams of the Unknot, arxiv.
  with Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler, Clément Maria, Saul Schleimer, Eric Sedgwick and Jonathan Spreer.
  
• Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries, arxiv.
  with Erin Wolf Chambers, Francis Lazarus and Salman Parsa.
  SOCG 2021
• Tightening Curves on Surfaces Monotonically with Applications, arxiv.
  with Hsien-Chih Chang.
  SODA 2020.
• Link Crossing Number is NP-hard, arxiv.
  with Marcus Schaefer and Eric Sedgwick.
  Journal of Knot Theory and its Ramifications, Vol. 29, No. 06, 2020.
  
• Homotopy height, grid-major height and graph-drawing height, arxiv.
  with Therese Biedl, Erin Wolf Chambers, David Eppstein and Tim Ophelders.
  GD 2019.
• Almost tight lower bounds for hard cutting problems in embedded graphs, arxiv.
  with Vincent Cohen-Addad, Éric Colin de Verdière and Dániel Marx.
  SOCG 2019. Best paper award.
  Journal of the ACM, Volume 68, Issue 4, 2021.
• The unbearable hardness of unknotting, arXiv.
  with Yo'av Rieck, Eric Sedgwick and Martin Tancer.
  SOCG 2019.
  Advances in Mathematics, Volume 381, 2021.
  
• On the tree-width of knot diagrams, arXiv.
  with Jessica Purcell, Saul Schleimer and Eric Sedgwick
  Journal of Computational Geometry, Vol. 10, No. 1 (2019), pp. 164-180.
  
• Constructing monotone homotopies and sweepouts, arXiv.
  with Erin Wolf Chambers, Gregory R. Chambers, Tim Ophelders and Regina Rotman.
  Journal of Differential Geometry. 119(3), 383--401, November 2021.
  
• Embeddability in R3 is NP-hard, arXiv.
  with Yo'av Rieck, Eric Sedgwick and Martin Tancer. SODA 2018.
  Journal of the ACM, Volume 67, Issue 4, 2020.
  
• Minimizing Intersections of Curves on Surfaces via Local Moves, Publisher, PDF.
  with Hsien-Chih Chang, Jeff Erickson, David Letscher, Saul Schleimer, Eric Sedgwick, Dylan Thurston and Stephan Tillmann.
  SODA 2018.
  
• The Bane of Low-Dimensionality Clustering, arXiv.
  with Vincent Cohen-Addad, Eva Rotenberg and Alan Roytman.
  SODA 2018.
  
• On the complexity of optimal homotopies, arXiv.
  with Erin Wolf Chambers and Tim Ophelders.
  SODA 2018.
  
• A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals, arXiv.
  with Vincent Cohen-Addad and Éric Colin de Verdière.
  SODA 2018.
  SIAM Journal of Computing, Volume 50, pp.1-31, 2021.
  
• Noeuds, mouvements de Reidemeister et algorithmes (d'après Lackenby), in French, Bourbaki PDF, Gazette PDF, YouTube.
  Séminaire Bourbaki, Astérisque, volume 407, Société Mathématique Française, pp. 27--52 (2019).
  Shorter version in Gazette des Mathématiciens, October 2018.
  
• Finding non-orientable surfaces in 3-manifolds, arXiv.
  with Benjamin A. Burton and Uli Wagner. SOCG 2016.
  Discrete and Computational Geometry, Volume 58, Issue 4, 871--888, 2017.
  
• Shortest path embeddings of graphs on surfaces, arXiv.
  with Alfredo Hubard, Vojtěch Kaluža and Martin Tancer. SOCG 2016.
  Discrete and Computational Geometry, Volume 58, Issue 4, 921--945, 2017.
  
• On the complexity of immersed normal surfaces, arXiv, Extended abstract, Publisher.
  with Benjamin A. Burton and Éric Colin de Verdière.
  Geometry & Topology, Volume 20, 1061-1083, 2016. An extended abstract was previously presented at EuroCG 2014.
  
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface, PDF, arXiv, Publisher.
  with Vincent Viallat Cohen-Addad.
  ESA 2015
  
• Discrete systolic inequalities and decompositions of triangulated surfaces, Published version, arXiv, Conference version.
  with Éric Colin de Verdière and Alfredo Hubard. Discrete and Computational Geometry, April 2015, Volume 53, Issue 3, pp. 587--620.
  A preliminary version appeared in the proceedings of SoCG 2014.
  
• Testing graph isotopy on surfaces, arxiv, Publisher.
  with Éric Colin de Verdière. Discrete and Computational Geometry, January 2014, Volume 51, Issue 1, Pages 171--206.
  A preliminary version appeared in the proceedings of SoCG 2012.
  
• Dimension reduction for finite trees in L1, arxiv, Publisher.
  with James R. Lee and Mohammad Moharrami. Discrete and Computational Geometry, December 2013, Volume 50, Issue 4, Pages 977--1032.
  A preliminary version appeared in the proceedings of SODA 2012.
  

Other Works

• De la carte au territoire ? (French, 2014)
  wit Éric Colin de Verdière. Images des Mathématiques, CNRS.
  Vulgarization article about Testing graph isotopy on surfaces above.
• Topics in Low-Dimensional Computational Topology, PDF.
  PhD Thesis, under the supervision of Eric Colin de Verdière.
  

Teaching

Computational aspects of geometry and topology, Master 2 cours at UGE, Maths-CS track, 2021-2022, co-taught with Frédéric Meunier.
Lecture notes, updated after each course.

Algorithms and combinatorics of geometric graphs, Master 2 course in Paris, 2020-2021, co-taught with Vincent Pilaud.
Lecture notes. First exercise sheet, Solution.

Algorithmique at ESIPE, exercise and practical sessions. 2019-2021.

Computational Topology, Master 2 course at ENS Lyon, 2016-2018, co-taught with Francis Lazarus.
Full Lecture Notes.

Supervision

Corentin Lunel (PhD, 2021-, with Pierre Dehornoy).

Jean Chartier (PhD, 2020-, with Laurent Hauswirth and Stéphane Sabourau).

Niloufar Fuladi (PhD, 2020-, with Éric Colin de Verdière and Alfredo Hubard).

Chenglin Fan (Post-doc, 2019-2020, with Vincent Cohen-Addad).

Grants

I am or have been a member of the ANR projects 3DMAPS, GATO, FOCAL, MINMAX and SoS.

Service

I co-organize (with Alfredo Hubard, Arnau Padrol and Lionel Pournin) the Paris Seminar on Discrete and Computational Geometry.

Editor of Computing in Geometry and Topology, a new diamond open access journal.

Program committees: Prix de thèse Gilles Kahn, EuroCG 2020, WADS 2019, SOCG 2017. Member of the scientific board of GT CoA.

I have co-organized (with Ulrich Bauer and Uli Wagner) the 9th Minisymposium on Computational Topology.

I have co-organized (with Francis Lazarus and Boris Thibert) the French Computational Geometry Days 2020.