Loria
bureau B166
615 rue du jardin botanique
54600 Villers-les-Nancy
xavier.goaoc@loria.fr
(+33) 3 54 95 85 37
Teaching
École des Mines, Campus Artem
bureau R329
CS 14234
54042 Nancy cedex
xavier.goaoc@univ-lorraine.fr
(+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*.
En 1A Mines, algorithmes et complexité
En 2A Mines, architecture des ordinateurs
En 2A Mines, introduction aux blockchains
En M2, modélisation géométrique et planification de trajectoire
En 5A Polytech, algorithmes de consensus et blockchains
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)
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. I am particularly
interested in its interactions
with topology, probability
and extremal combinatorics.
Convex hulls of random order types, X. Goaoc and E. Welzl. Journal of the ACM, 70(1): 1--47, 2023. (A preliminary version received the best paper award at SoCG'20.)
Shellability is NP-complete, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Journal of the ACM 66(3): article 21, 2019. (A preliminary version received the best paper award at SoCG 2018, pp 41:1--15.)
Simplifying inclusion-exclusion formulas, X. Goaoc, J. Matousek, P. Paták, Z. Safernová, and M. Tancer. Combinatorics, Probability and Computing 24(2): 438--456, 2015.
Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.)
Bounding Helly numbers via Betti numbers, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. A Journey Through Discrete Mathematics, pp 407--447, 2017. (A preliminary version appeared in the proceedings of SoCG 2015, pp 507--521.)
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.
Convexité combinatoire (in french), X. Goaoc. Informatique mathématique, une photographie en 2020, pp 151--201, 2020.
Shellability is NP-complete, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Journal of the ACM 66(3): article 21, 2019. (A preliminary version received the best paper award at SoCG 2018, pp 41:1--15.)
Simplifying inclusion-exclusion formulas, X. Goaoc, J. Matousek, P. Paták, Z. Safernová, and M. Tancer. Combinatorics, Probability and Computing 24(2): 438--456, 2015.
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...
Convex hulls of random order types, X. Goaoc and E. Welzl. Journal of the ACM, 70(1): 1--47, 2023. (A preliminary version received the best paper award at SoCG'20.)
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.
Bounding Helly numbers via Betti numbers, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. A Journey Through Discrete Mathematics, pp 407--447, 2017. (A preliminary version appeared in the proceedings of SoCG 2015, pp 507--521.)
Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.)
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.
Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.)
Line transversals to disjoint balls, C. Borcea, X. Goaoc, and S. Petitjean. Discrete & Computational Geometry 39(1-3): 158--173, 2008. (A preliminary version appeared in the proceedings of SoCG 2007.)
Inflating balls is NP-hard, G. Batog and X. Goaoc. International Journal of Computational Geometry and Applications 21(4): 403--415, 2011.
Helly-type theorems for approximate covering, J. Demouth, O. Devillers, M. Glisse, and X. Goaoc. Discrete & Computational Geometry 42(3): 379--398, 2009. (A preliminary version appeared in the proceedings of SoCG 2008.)
Untangling a Planar Graph, X. Goaoc, J. Kratochvil, Y. Okamoto, C.-S. Shin, A. Spillner, and A. Wolff. Discrete & Computational Geometry 42(4): 542--569, 2009. (A preliminary version appeared in the proceedings of Graph Drawing 2007.)
