Agenda

Département
Langue
Date
Thématique
2021

December

  • 10:45
    11:45

    Torsten Mütze Seminar (on Zoom): ““Efficient generation of elimination trees and Hamilton paths on graph associahedra”

    An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm (see www.combos.org/elim). This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.

    GT : Connexion (Zoom) : https://u-bordeaux-fr.zoom.us/j/89261618564?pwd=RlNWdldvN1dYMDdCQ2pYSVBUdE9xdz09

    Mot de passe : s’adresser au contact

    English
    LaBRI salle 76 (+ visioconférence zoom)
  • 14:00
    18:00

    Tidiane Sylla PhD: «User-centric security and privacy in the IoT»

    Today, the numerous applications of the Internet of Things (IoT) can significantly improve the daily life of users. Thanks to these applications, it is possible to remotely control the various devices in the home, monitor a patient's vital signs and automatically alert their doctor in case of a problem. However, security and privacy issues prevent users from fully trusting these applications, which can have the effect of slowing down the overall adoption of these technologies and their widespread deployment. To address these security and privacy issues, several solutions have been proposed. However, several challenges remain to be addressed to enable widespread adoption of these applications. The user-centric approach seems to be very relevant to address many of these challenges. To provide user-centric security and privacy and enable support for many IoT applications, the work in this thesis proposes to adapt the implementation of security and privacy mechanisms based on the user context. First, this thesis presents the CASPaaS (Context-Aware Security and Privacy as a Service) architecture. This context-aware security and privacy architecture for the IoT is based on the 'as a service' approach. It ensures dynamic and personalized adaptation of security and privacy services according to the user's context. Thanks to the 'as a service' design, this architecture is characterized by a high degree of flexibility that allows it to support a wide range of IoT many IoT applications. In a second step, this thesis presents a system to manage the security and reliability of the CASPaaS architecture itself. This system, called SETUCOM (SEcure and TrUstworthy COntext Management) manages the security of the contextual data exchanged within the CASPaaS architecture as well as the trust of the data sources. This allows to mitigate a large number of attacks that can lead to the malfunctioning of our CASPaaS architecture.
    In a third step, this thesis presents a new decentralized context-sensitive authorization management system for the IoT. This system, also based on the 'as a service' approach, offers the user a dynamic, decentralized and simple authorization management. Finally, this thesis focuses on the deployment of the CASPaaS service closer to the users based on an Edge Computing infrastructure. In this context, we propose a new dynamic placement strategy for this service. This strategy uses artificial intelligence techniques to ensure an efficient placement while optimizing the different performances (network, service, Edge nodes capacities, placement process itself, etc.).

    Français
    Amphi LaBRI
  • 09:30
    14:00

    Alena Shilova PhD: "Strategies for saving memory during learning in deep neural networks"

    Artificial intelligence is a field that has received a lot of attention recently. Its success is due to the progress of Deep Learning, a sub-field that brings together machine learning methods based on neural networks. These neural networks have proven to be effective in solving very complex problems in different domains. However, their effectiveness in solving problems depends on a number of factors: the architecture of the model, its size, how and where the training was performed. Most studies indicate that larger models achieve better accuracy, but they are also more expensive to train. The main challenges are related to the computational power and limited memory of the machines: if the model is too large, it may take a long time to learn (days or even months) or, in the worst case, it may not even fit in memory. During the learning process, it is necessary to store both the weights (model parameters), the activations (intermediate computed data) and the optimizer states.
    This situation offers several opportunities to deal with memory problems, depending on their origin. Learning can be distributed across multiple resources on the computational platform, and different parallelization techniques offer different ways to distribute memory. In addition, data structures that remain inactive for a long period of time can be temporarily offloaded to a larger storage space, with the possibility of recovering them later (offloading strategies). Finally, activations that are computed at each iteration can be deleted and recomputed several times during the iteration (rematerialization strategies). Memory saving strategies usually induce a time overhead compared to direct execution, therefore optimization problems must be considered to choose the best approach for each strategy. In this manuscript, we formulate and analyze optimization problems in relation to various methods to reduce memory consumption during the learning process. In particular, we focus on rematerialization, activation offloading and pipelined model parallelism strategies; for each of them, we design optimal solutions under a set of assumptions. Finally, we propose a fully functional tool called rotor that combines activation offloading and rematerialization and can be used for training large models with minimal overhead in PyTorch, models that would otherwise not fit in memory.

     

    English
    Amphi LaBRI
  • 14:30
    18:00

    Cindy Becher's PhD: "Disambiguation of the visualization and manipulation of occluded virtual 3D objects in Augmented Reality: application to a case of management of plans of sensitive buried networks"

    This PhD thesis presents the work that allowed us to develop an efficient and user-optimized Augmented Reality system for the management of sensitive underground networks. More and more institutions require mapping of underground networks in order to avoid accidents and damage to existing structures. In addition to the fact that these plans are sometimes incorrect or even non-existent, they are difficult to interpret in the field. This is why we propose a complete system, allowing the exploitation of the plans of buried networks in Augmented Reality. This system has been designed to be used in-situ, in real time, by the same user. It allows the visualization, the selection, the modification of textual attribute data and of the position of the buried networks, clear, effective and little tiring. In particular, this system allows to disambiguate the semantic interpretation of virtual objects of buried networks displayed in Augmented Reality. We conducted experiments to compare four visualization modes and their influence on the perception of virtual objects. Also, we studied two selection modes and two annotation modes in order to understand the possible benefits of a system composed of two devices: an Augmented Reality headset and a smartphone. We also studied the manipulation of virtual objects representing buried networks using a smartphone as a tangible interactor. This thesis was realized within the framework of a CIFRE grant (Convention Industrielle de Formation à la Recherche) by the ANRT, in collaboration with the company SIG-IMAGE and the two research laboratories ESTIA Institute of Technology and the Laboratoire Bordelais de Recherche en Informatique.

    YouTube : https://youtu.be/N002RiL1UdM

    Français
    Amphi 32 (ESTIA à Bidart)
  • 18:15
    19:30

    Aurélie Bugeau (LaBRI, Bordeaux University) will present a seminar: “Digital and environment”

    While digital technologies are often cited as indispensable for the ecological transition, their effects on the environment should not be ignored. transition, their effects on the environment should not be ignored. In a context of context of increasing digitization and virtualization of our society, we will review the various ecological ecological, geopolitical and societal impacts of digital technology. We will give concrete tracks of solutions to reduce solutions to reduce these impacts.

    The program of the seminar is available on the web page dedicated to the Graduate Program Numeric.

    Français
    Amphi LaBRI
  • 10:00
    14:00

    Dimitri Lajou PhD: "On various graph coloring problems"

    Dimitri Lajour (CombAlgo department) will submit his thesis entitled: "On various graph coloring problems"

    Amphi A, Bât A29
  • Alexandre Blanche PhD: « Decomposition into Gallai paths in planar graphs»

    This thesis is part of the computer science field of graph theory, and deals with a question posed in 1968 by Tibor Gallai, still unanswered today. Gallai conjectured that the edges of any connected graph with n vertices could be partitioned into [(n+1)/2] paths. Although this conjecture was attacked and partially solved over the years, the property has only been proved for very specific classes of graphs, such as graphs whose even degree vertices form a forest (Pyber, 1996), graphs of degree at most 5 (Bonamy, Perrett, 2016), or graphs of tree width at most 3 (Botler et al., 2018). Planar graphs are graphs that can be plunged into the plane, i.e. drawn without edge crossings. This is a well-known class in graph theory, and widely studied. Botler, Jiménez and Sambinelli have recently confirmed the conjecture in the case of planar graphs without triangles. Our result consists in a proof of the conjecture on the general class of planar graphs. This class is notably more general than the previous results, and from our point of view constitutes an important contribution to the study of the Gallai conjecture. Specifically, we work on a stronger version of the conjecture, proposed by Bonamy and Perrett in 2016, which states that related graphs with n vertices can be decomposed into [n/2] paths, except for a family of dense graphs. We confirm this conjecture in the case of planar graphs, by proving that any planar graph except K3 and K5- (K5 minus one edge) can be decomposed into [n/2] paths. The proof is divided into three parts: the first two show the main lemma of the proof, which restricts the structure of a hypothetical counterexample with a minimum of vertices, and the third part uses this lemma to show that such a counterexample does not exist.

    Français
    Amphi LaBRI
  • 17:15
    18:30

    Xavier Caruso (IMB, Bordeaux University) will present a seminar: "The promise of the quantum computer"

    At the beginning of the 20th century, physics underwent two major revolutions with the theory of relativity and quantum mechanics, which forever changed our conception of the world at all scales. Quantum mechanics concerns the infinitely small and has consequences that surprised the greatest physicists of the time. One of them is the famous EPR paradox which seems to defy the theory of general relativity since it implies the possibility, for two people far away in space, to agree instantaneously on a bit of information. However, quantum mechanics is one of the most proven theories of modern physics with many experiments confirming it with phenomenal accuracy. In the middle of the 20th century, Feynman put forward the idea of taking advantage of the quantum properties of matter to build computers that are more powerful than our classical machines. Thus, a model of the quantum computer was proposed and the first quantum algorithms were designed. Feynman's vision was fabulously confirmed after the work of Deutsch, Jozsa, Shor and Grover who showed that several classical mathematical problems known to be difficult (including the factorization of integers) could be solved efficiently in the quantum world. These results have an even greater impact today, as they call into question the security of the most widely used cryptographic protocols in the modern world and the race to build the first quantum computer has already begun.

    The program of the seminar is available on the web page dedicated to the Graduate Program Numeric.

    Français
    Amphi LaBRI
  • Paul Beziau PhD (Satanas department): "Load balancing in hierarchical solvers for massively parallel machines"

    Paul Beziau will submit his thesis entitled: "Load balancing in hierarchical solvers for massively parallel machines"

    Français
  • 14:00
    18:00

    Camille Benaroch PhD: "Contribution to the understanding of mental task-based BCI performance using predictive computational models"

    Camille Benaroch (I&S department) will submit her thesis entitled: "Contribution to the understanding of BCI performance based on mental tasks using predictive computational models".

    Salle Ada Lovelace (Inria)