Author: David COUDERT

New team member: Emanuele Natale

Emanuele Natale

Welcome to our new team member: Emanuele Natale.

Emanuele Natale got his B.Sc. in Mathematics in 2011 and M.Sc. in Computer Science in 2013, from University of Rome “Tor Vergata”, and his Ph.D. in Computer Science in 2017 from Sapienza University of Rome under the supervision of Andrea Clementi and Riccardo Silvestri.
During his Ph.D. he was a visiting student at IRIF (LIAFA) in Paris, hosted by Pierre Fraigniaud, and at the Simons Institute for the Theory of Computing of U.C. Berkeley, hosted by Luca Trevisan.
During his graduate studies he has been awarded the Best PhD Paper in CS at Sapienza 2015 (ex-equo), the Best Student Paper at the European Symposium of Algorithms (2016), the Outstanding PhD Student of Year 2015-2016 Award of the CS PhD School of Sapienza (ex-equo), and the Best PhD Thesis Award by the Italian Chapter of EATCS (2017).
After his Ph.D. he joined Kurt Mehlhorn’s Algorithms and Complexity Department at the Max Planck Institute for Informatics in Saarbrücken, and was again at the Simons Institute for the Theory of Computing in 2018 as a holder of Simons Fellowship.
In January 2019, he started his position as a permanent CNRS researcher joining the I3S laboratory, as a member of the COATI team jointly with INRIA.

HDR defense of Frédéric Giroire

HDR Frédéric Giroire

  • Title: “Optimisation des infrastructures réseaux. Un peu de vert dans les réseaux et autres problèmes de placement et de gestion de ressources“
  • When: October 23, 2018 — 10:30
  • Where: Room Euler Violet, Inria Sophia Antipolis Méditerranée
  • Committee:

  • Abstract: In this thesis, I present a set of solutions to optimize network infrastructures. Pushed by the new sensitivity of the society, politics, and companies to energy costs and global warming, I investigated the question of how to build green networks. I first studied some practical scenarios to answer the question: how much energy could be saved for Internet Service Providers by putting into practice energy efficient protocols? It led me to study fundamental problems of graph theory.

    At the core of these energy efficient methods, there is a dynamic adaptation to the changes of demands, which is impossible to do in legacy networks which are mostly manually operated. The emergence of two new paradigms, software defined networking (SDN) and network function virtualization (NFV), leads to a finer control of networks and thus bears the promise to to put energy efficient solutions into practice. I thus studied how to use SDN to implement dynamic routing.

    My approach has been to use theoretical tools to solve problems raised by the introduction of new technologies or new applications. My tools come mainly from combinatorics and in particular from graph theory, algorithmics, optimization and probabilities. When I was able to propose new methods of resolution, I then tried to evaluate their practical impact by numerical evaluation, simulation or experimentation with realistic scenarios.

New team member: Alexandre Caminada

Alexandre Caminada

Welcome to our new team member: Alexandre Caminada.

Alexandre Caminada holds an engineering degree from ESIEA-Paris (1987), a M.Sc. in artificial intelligence from Paris XIII (1987) and a PhD in computer science from University of Montpellier (1993). He joined the National Center for Telecommunications Studies (CNET now Orange Labs) in 1993 to lead a European project and a research unit on mobile network optimization. In 2003, he joined University of Technology Belfort-Montbéliard (UTBM) as a university Professor where he held several responsibilities: head of the optimization research team, director of the training department of computer engineers, then director of the training and pedagogy of the institution. In 2017, he became the director of engineering school Polytech Nice Sophia. In September 2018 he joined Université Nice – Sophia Antipolis as a university Professor and is now a member of COATI. He has already supervised 22 PhD theses and has published numerous scientific publications (see dblp and google scholar).

PhD defense of William Lochet

PhD William Lochet

    • Title: “Sub-structures in digraphs”
    • When: July 19, 2018 — 14:00
    • Where: Inria Sophia Antipolis, Euler violet
    • Committee:

    • Abstract: The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening ofthis conjecture. Among other results, we prove that digraphs with large minimum outdegree contain large in-arborescences. We also prove that digraphs with large minimum outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs.
      This thesis also presents the proof of the Erdős-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3.
      Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression.

    • Titre: “Sous-structure dans les digraphes”

    • Résumé: Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l’existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu’il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d’abords question de montrer l’existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu’un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d’autre structures, pour des graphes dirigés fortement connexes.
      Cette thèse présente également la preuve de la conjecture de Erdős-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k.
      Pour finir, cette thèse présente la preuve de deux résultats, un sur l’orientation des hypergraphes et l’autre sur la coloration AVD, utilisant la technique de compression d’entropie.

Seminar by Robert E. Tarjan: Zip Trees

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Zip Trees
  • When: June 29, 2018 — 14:00
  • Where: I3S, Salle de conférence 007

  • Abstract: This talk will present the zip tree, a simple and efficient type of binary search tree. Zip trees use randomization to achieve balance. A zip tree can be viewed as a binary-tree representation of a skip list or as a variant of a treap. Insertion and deletion avoid the multiplicity of cases that arise in standard balanced trees. Zip trees can be adapted to exploit biased access distributions. Their simplicity makes them promising for concurrent use.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.

  • See the thread on Twitter

Cérémonie des Lauréats de prix d’excellence d’Université Côte d’Azur

Members of COATI participates to the 2017 edition of Cérémonie des Lauréats de prix d’excellence d’Université Côte d’Azur.

More pictures here.