Jean Cardinal

Professor
Université libre de Bruxelles
I am a professor of computer science at the Université libre de Bruxelles (ULB), in Brussels, Belgium, and co-director of the Algorithms Research Group.

My research is in the field of theoretical computer science and discrete mathematics. I am particularly interested in computational geometry, the branch of computer science devoted to the design and analysis of algorithms for problems involving geometric data. I also enjoy thinking about purely combinatorial structures such as graphs and partially ordered sets, most often with computational issues in mind. Some of my earlier works deal with data compression and problems in information theory.

I obtained my PhD from ULB in 2001, with a fellowship from the FNRS, after spending some time at the University of Washington. I have held visiting professorships at various institutions since then, the most recent ones being at ETH Zurich and Université Sorbonne Paris Nord. See my CV for more details.

I enjoy collaborative research, and met many of my coauthors at research workshops around the world, such as the Annual workshop on geometry and graphs, the Order and geometry workshop, or Gremo's workshop on open problems.

My papers can be found on DBLP, MathSciNet, zbMATH, ArXiv, Google Scholar, and our local repository DI-fusion. Here are some recent contributions:

  • A general technique for searching in implicit sets via function inversion, with Boris Aronov, Justin Dallant, and John Iacono, SOSA 2024.
  • The rotation distance of brooms, with Lionel Pournin and Mario Valencia-Pabon, European Journal of Combinatorics.
  • Inapproximability of shortest paths on perfect matching polytopes, with Raphael Steiner, IPCO 2023 and Mathematical Programming.
  • Improved Algebraic degeneracy testing, with Micha Sharir, SoCG 2023 and Discrete & Computational Geometry.
  • Combinatorial generation via permutation languages. V. Acyclic orientations., with Hung Phuc Hoang, Arturo Merino, and Torsten Mütze, SODA 2023 and SIAM Journal on Discrete Mathematics.
  • Efficient generation of elimination trees and graph associahedra, with Arturo Merino and Torsten Mütze, SODA 2022.
  • Competitive online search trees on trees, with Prosenjit Bose, John Iacono, Grigorios Koumoutsos, and Stefan Langerman, SODA 2020 and ACM Transactions on Algorithms.
  • And here are links to some recent online talks:

  • Diameter estimates for graph associahedra, Copenhagen-Jerusalem Combinatorics Seminar, July 7 2022.
  • Algorithms for approximate sparse regression and closest induced flats, NYU CG seminar, November 30, 2021.
  • Mathématiques discrètes et ordinateurs : Cendrillon et le Prince de l’informatique (in french), Académie Royale de Belgique, le 24 février 2021.
  • Flip distances between graph orientations, LA Combinatorics and Complexity Seminar, October 13, 2020.
  • Trees on trees, DIMAP Seminar, University of Warwick, October 7, 2020.