Arnaud de Mesmay

I am a CNRS researcher, working in the ADA team of Laboratoire d'Informatique Gaspard Monge at Université Gustave Eiffel, close to Paris. Before that, I worked at 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 Verdière.

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 arnaud.de-mesmay(at)univ-eiffel(dot)fr

Selected publications

A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals, arxiv.
with Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Alantha Newman and Tony Chang Wang.
SODA 2024
Fitting Metrics and Ultrametrics with Minimum Disagreements. arxiv.
with Vincent Cohen-Addad, Chenglin Fan and Euiwoong Lee. FOCS 2022.
SIAM Journal on Computing, Vol. 54, Issue 1, 2025.
Tightening Curves on Surfaces Monotonically with Applications, arxiv.
with Hsien-Chih Chang. SODA 2020.
ACM Transactions on Algorithms, Vol. 18, Issue 4, October 2022.
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.
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.

Complete list of publications (click to expand)

Crossing numbers of dense graphs on surfaces, arxiv.
with Alfredo Hubard and Hugo Parlier.
Hard Diagrams of Split Links, arxiv.
with Corentin Lunel and Jonathan Spreer.
SoCG 2025.
Hopf Arborescent Links, Minor Theory, and Decidability of the Genus Defect, arxiv.
with Pierre Dehornoy and Corentin Lunel.
SoCG 2024.
Representing Matroids over the Reals is ER-complete, arxiv.
with Eunjung Kim and Tillman Miltzow.
Discrete Mathematics & Theoretical Computer Science, 2024.
A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals, arxiv.
with Vincent Cohan-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Alantha Newman and Tony Chang Wang.
SODA 2024
Degenerate crossing number and signed reversal distance, arxiv.
with Niloufar Fuladi and Alfredo Hubard.
GD 2023
Universal families of arcs and curves on surfaces, arxiv.
with Niloufar Fuladi and Hugo Parlier.
Israel Journal of Mathematics, 2025.
A structural approach to tree decompositions of knots and spatial graphs, arxiv.
with Corentin Lunel.
SOCG 2023. Accepted in Algebraic and Geometric Topology.
Voting algorithms for unique games on complete graphs, arxiv.
with Antoine Méot, Moritz Mühlenthaler and Alantha Newman.
SOSA 2023
Fitting Metrics and Ultrametrics with Minimum Disagreements. arxiv.
with Vincent Cohen-Addad, Chenglin Fan and Euiwoong Lee. FOCS 2022.
FOCS 2022. SIAM Journal on Computing, Vol. 54, Issue 1, 2025.
Short Topological Decompositions of Non-Orientable Surfaces, arxiv.
with Niloufar Fuladi and Alfredo Hubard. SOCG 2022.
Discrete and Computational Geometry, 2023.
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres, arxiv.
with Jean Chartier. SOCG 2022.
Discrete and Computational Geometry, Volume 71, pages 95–120, 2024.
Distributed coloring and the local structure of unit-disk graphs, arxiv.
with Louis Esperet and Sébastien Julliot. ALGOSENSORS 2021.
Theoretical Computer Science, Volume 944, Article 113674, 2023.
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.
Experimental Mathematics, 2023.
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries, arxiv.
with Erin Wolf Chambers, Francis Lazarus and Salman Parsa. SOCG 2021.
Discrete and Computational Geometry, Vol. 70, pp. 323-354, 2022.
Tightening Curves on Surfaces Monotonically with Applications, arxiv.
with Hsien-Chih Chang. SODA 2020.
ACM Transactions on Algorithms, Vol. 18, Issue 4, October 2022.
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. EuroCG 2014.
Geometry & Topology, Volume 20, 1061-1083, 2016.
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, Corrigendum.
with Éric Colin de Verdière and Alfredo Hubard. SoCG 2014.
Discrete and Computational Geometry, April 2015, Volume 53, Issue 3, pp. 587--620.
Testing graph isotopy on surfaces, arxiv, Publisher.
with Éric Colin de Verdière. SoCG 2012.
Discrete and Computational Geometry, January 2014, Volume 51, Issue 1, Pages 171--206.
Dimension reduction for finite trees in L1, arxiv, Publisher.
with James R. Lee and Mohammad Moharrami. SODA 2012.
Discrete and Computational Geometry, December 2013, Volume 50, Issue 4, Pages 977--1032.

Other Works

Interactions between algorithms, geometry and topology in low dimensions, HAL, PDF.
Habilitation thesis, 2022.
Topics in Low-Dimensional Computational Topology, HAL, PDF.
PhD Thesis, under the supervision of Eric Colin de Verdière, 2014.

Outreach

Démêler les noeuds avec des boucles (French, 2025), Interstices.
Outreach article about knot theory and algorithms.
De la carte au territoire ? (French, 2014), Images des Mathématiques.
with Éric Colin de Verdière.
Outreach article about Testing graph isotopy on surfaces above.

Recent teaching

Journées Mathématiques X-UPS, Polytechnique, 2025. Draft of lecture notes in French on matroid algorithms and log-concave polynomials.

Programmation web, L1 UGE, 2023-2024 (in French).

A Master 2 course on embedded graphs, taught alternatively at MPRI and UGE:

2023-2024: Master 2 course at UGE, Maths-CS track. Geometry, co-taught with Laurent Hauswirth.
Lecture notes (updated after each class), Homework, Some exercises.
2022-2023: Algorithms and combinatorics of geometric graphs, Master 2 course in Paris (MPRI) co-taught with Luca Castelli-Aleardi and Vincent Pilaud.
Lecture notes, Homework.
2021-2022: Master 2 course at UGE, Maths-CS track. Computational aspects of geometry and topology, co-taught with Frédéric Meunier.
Lecture notes. Some exercises.
2020-2021: Algorithms and combinatorics of geometric graphs, Master 2 course in Paris (MPRI), co-taught with Vincent Pilaud.
Lecture notes. First exercise sheet, Solution.

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

Supervision

Jean Chartier (PhD, 2020-2025), with Laurent Hauswirth and Stéphane Sabourau). Now ATER at UGE.

Corentin Lunel (PhD, 2021-2024, with Pierre Dehornoy). Now post-doc with INRIA in Montpellier .

Niloufar Fuladi (PhD, 2020-2023, with Alfredo Hubard). Now post-doc at LORIA.

Chenglin Fan (Post-doc, 2019-2020, with Vincent Cohen-Addad). Now assistant professor at Seoul National University.

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 and Lionel Pournin) the Paris Seminar on Discrete and Computational Geometry.

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

Program committees: SOSA 2026, STACS 2025, STOC 2024, CG:YRF 2023, SOCG 2023, SODA 2023, Prix de thèse Gilles Kahn 2021-2023, EuroCG 2020, WADS 2019, SOCG 2017.

Member of the scientific board of GT CoA. Head of the ADA team of LIGM. In charge of the Suivi Doctoral at LIGM. Member of the lab council of LIGM.

Some events I have (co-)organized: 4th Workshop Complexity and Algorithms (IHP, 2024, with Sébastien Tavenas), Mini-Symposium on Graphs Embedded on Surfaces (within Curves & Surfaces 2022), Structures on Surfaces (CIRM, 2022, with Vincent Despré, Alfredo Hubard, Hugo Parlier and Monique Teillaud), Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar, 2022, with Maike Buchin, Anna Lubiw and Saul Schleimer), 9th Minisymposium on Computational Topology (with Ulrich Bauer and Uli Wagner), French Computational Geometry Days 2020 (with Francis Lazarus and Boris Thibert).