Guillaume Ducoffe, PhD

Scientific Researcher at National Institute of Research and Development in Informatics (I.C.I.), Romania

guillaume `dot' ducoffe `at' ici `dot' ro

About myself

I am part of a joint team between ICI and The Research Institute of the University of Bucharest (I.C.U.B., of which I received a postdoc grant). Before that, I received my PhD thesis on December 9th, 2016 from Université Côte d'Azur (U.C.A.), France. My main research area is algorithmic graph theory. I am especially interested in the following topics:

  • Computation in Large Graphs: design of preprocessing methods and parameterized algorithms for fundamental problems such as Diameter, Maximum Matching etc (``FPT in P''). I also complement these results with conditional lower-bounds on the complexity of these problems.
  • Information-propagation in real-life graphs: in-depth study of metric tree-likeness in graphs (i.e., Gromov Hyperbolicity and its relatives), that are related to fundamental properties such as congestion and are useful in the design of compact geometric routing schemes. I also study the information-sharing problem from a game-theoretic point of view (mostly through the study of coloring games and Hedonic games).
  • Online targeting detection: design of fast and theoretically certified algorithms for identifying how a given advertiser online, represented as a black-box, targets some sensitive information such as gender, race, etc. This can be reduced to an interesting variation of PAC-learning k-juntas.
  • Combinatorics: some variations of graph coloring such as proper connectivity (with applications in password sharing), graph indices such as Randic numbers (with applications in chemistry), etc.

An (almost up to date) resume can be found here.



I am teaching the Master course ``Performance evaluation of information systems'' (University of Bucharest, 2018/2019).

  • The teaching material for this class can be found here.

I am teaching the Bachelor course ``Graph algorithms'' (University of Bucharest, 2018/2019)

  • The teaching material for this class can be found here.

Past teaching experiences are mentioned in my resume.