Xavier Goaoc

Professor of computer science
Université de Lorraine, Nancy

Welcome to my professional web page. Here you'll find information on my research and my teaching activities.

Picture by Otfried Cheong

Since 2018, I work at at Université de Lorraine in Nancy.

I am affiliated with the department of computer science & engineering of École des Mines de Nancy, where I do most of my teaching.

I am also a member the Gamble research team, joint between the LORIA laboratory and the INRIA research center.

Here is a short cv.


bureau B166
615 rue du jardin botanique
54600 Villers-les-Nancy

(+33) 3 54 95 85 37


École des Mines, Campus Artem
bureau R329
CS 14234
54042 Nancy cedex
(+33) 3 72 74 49 62

  • algorithmes et complexité. Cours de tronc commun de 1ère année (9x3h). Introduit à l'informatique théorique (modèles de calcul, conception et analyse d'algorithmes, complexité des problèmes, NP-difficulté).

  • architecture des ordinateurs. Cours de 2ème année du département informatique (7x3h). Aborde les hiérarchies mémoire, l'assembleur x86 et l'analyse de code compilé par gcc, le pipeline et la prédiction de branchement, la vectorisation.

  • introductions aux blockchaines. Cours électif de 2ème année (7x3h). Aborde le hachage et les signatures cryptographique, les principes de calcul distribué, les principes de la blockchaine de bitcoin, le théorème de Fischer, Lynch, Paterson et le théorème Lamport-Shostak-Pease, les algorithmes Paxos et BBA*.
  • algorithmes et complexité, cours de tronc commun scientifique, 1ère année d'Ingénieur Civil des Mines
  • architecture des ordinateurs, cours de département informatique, 2ème année d'Ingénieur Civil des Mines
  • introduction aux blockchains, cours électif transverse, 2ème année d'Ingénieur Civil des Mines
  • modélisation géométrique et planification de trajectoire, cours de M2 informatique (parcours AVR), partagé avec Francis Colas et Olivier Devillers
  • algorithmes de consensus et blockchains, cours de 5ème année de spécialité programmation et réseau à Polytech Nancy
  • 2021-2022 : architecture avancée, introduction aux blockchaines, algorithmes et complexité, consensus et blockchains
  • 2020-2021 : algorithmique avancée, architecture avancée, introduction aux blockchaines, algorithmes et complexité, algorithmique distribuée, apprentissage automatique (TD), recherche opérationnelle (TD)
  • 2019-2020 : algorithmique avancée, architecture avancée, introduction aux blockchaines, recherche opérationelle (TD), algorithmique-programmation (TD)
  • 2018-2019 : algorithmique avancée, architecture avancée
  • 2017-2018 : architecture avancée, mathématiques discrètes (isopérimétries), fondements de l'optimisation
  • 2016-2017 : architecture avancée, mathématiques discrètes (isopérimétries)
  • 2015-2016 : architecture des ordinateurs, mathématiques discrètes (géométrie)
  • 2014-2015 : optimisation combinatoire, architecture des ordinateurs
  • 2013-2014 : architecture des ordinateurs, probabilités pour informaticien, programmation en C, optimisation combinatoire, mathématiques discrètes pour informaticiens

My research is in algorithms and discrete mathematics, more precisely in the area of discrete and computational geometry.

Most of my work is on discrete structures that arise from geometric data, for instance convex hull of point sets or intersection patterns of families of sets. I try to understand how the geometry of the data influences these structures, with an emphasis on properties related to computation (e.g. Helly-type theorems which play a role in optimization).

I often use topology (e.g. the nerve theorem or non-embedability results), probabilities (e.g. negative association or discrete-continuous equivalences) and combinatorics (e.g. Ramsey theory or forbidden structures)... and of course geometry in many forms. I am particularly fond of the line geometry pioneered by Plücker, Klein, Grassmann...

Here is a complete list of my publications (by type, reverse-chronological).

Below are my main publications organized by topics. You'll also find some of my papers on arXiv and on HAL.

INRIA associate team FIP

(A handful of papers appear in more than one topic.)

Uli Wagner proposed an homological version of graph minors for simplicial complexes. Here are some applications of this notion.
Abstract simplicial complex are elementary combinatorial structures, really a subclass of hypergraphs, that, like planar graphs, can be interpreted as triangulations of topological spaces. Their study combines combinatorics and topology beautifully.
These papers investigate the combinatorial complexity of discrete structures (such as polytopes) defined by random point sets.
Order types are combinatorial structures that arise from finite (planar) point sequences, in the same way as permutations arise from finite sequences of real numbers. I am interested in random generation methods that produce "interesting" order types. This proves surprisingly difficult...
Combinatorial convexity studies the intersection patterns of families of convex sets, with a particular attention to the systems of convex hulls of finite subsets of a point set. It grew out of the theorems of Helly, Radon and Carathéodory and flourished in a rich and beautiful theory with surprising connections. I am interested in relaxing convexity into weaker topological assumptions.
Combinatorial convexity can be extended by considering not only points common to families of convex sets, but lines piercing families of convex sets. See here for a sample. I am interested in geometric permutations and worked on some conjectures of Danzer.
Line geometry is also useful for the analysis of geometric models of imaging systems. Here are some examples.