Calendrier des animations scientifiques

The //disjoint paths logic//, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate dp$_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the //scattered disjoint paths logic//, FOL+SDP, where we further consider the atomic predicate $s$-sdp$_k(x_1,y_1,\ldots,x_k,y_k),$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.

Joint work with Petr Golovach and Dimitrios M. Thilikos

Notre étude a pour objectif de créer des graphes de routage pour des espaces intérieurs complexes (dit routage indoor). Nous nous inspirons de la technique de navigation Mesh – très présente dans les jeux vidéos pour aider les différentes intelligences artificielles à trouver leur chemin dans des cartes -. Cette technique consiste à partitionner un polygone quelconque en un ensemble de polygones convexes afin de créer un graphe de visibilité entre ces polygones. Nous nous basons sur un article de Ramon et al. présentant un algorithme simple et automatique pour réaliser cette procédure, et nous proposons des pistes d’amélioration pour ce dernier permettant d’obtenir des partitions avec des propriétés plus intéressantes pour le problème de routage indoor.

In this lecture we classify quantifiers according to non-emptiness (i.e. always an object is denoted and according to dimension. For non-empty quantifiers Skolemization and some sort of epsilon calculus is always possible. This is not possible for empty quantifiers however positive results concerning eg the prenex fragment are possible (We choose as most natural example in this respect Gödel quantifiers.) Furthermore we classify quantifiers after dimension and show that in a proof-theoretic aspect global views on proofs which contradict Hilbert’s pardigma are necessary. This holds for quantifier macros and a fortiori for (partial
calculi for) Henkin quantifiers

The minimum-membership set cover (MMSC) problem is a variant of the traditional set cover problem. Given a universe S and a collection of sets R, the goal of MMSC is to select a subset R of R such that every element in S is covered by R. Instead of minimizing the size of R as in the usual set cover problem, the goal of MMSC is to minimize the maximum degree of an element of S in R. This problem was introduced by Kuhn et al. in 2005, where they gave a log(n) approximation in polynomial time and showed that it was the best approximation ratio we could hope for under standard complexity assumptions.
In this talk, we will focus on the problem where the sets S and R represent geometric objects. This setting was first studied by Erlebach and van Leeuwen in 2008, where they showed NP-hardness for approximating the problem with a ratio less than 2 on unit disks and unit squares. They also gave a 5-approximation algorithm that runs in polynomial time when OPT is bounded (n^O(OPT)) for the case of unit squares. The main goal of the talk will be to present a constant factor approximation algorithm that runs in (truly) polynomial time.

This is based on joint work with S. Bandyapadhyay, S. Saurabh, and J. Xue.

In this talk, we argue why building green software requires accurate observation and analysis, in a holistic vision including technical optimizations and human actors alike. We present our latest research on energy monitoring in multi-platform hardware and software (CPS, servers and mobile), and analyzing the impact of code and usage on software energy efficiency.

In this presentation, I will focus on security and privacy in the Internet of Things (IoT), using modern asymmetric cryptography (e.g. RSA, Diffie-Hellman) and post-quantum cryptography (e.g., based on lattices).

IoT is an environment with its challenges and limitations. Application domains are diverse and heterogeneous (e.g., eHealth versus wearable technology). Smart devices forming IoT networks often have constrained resources in terms of computation, communication, and storage. While IoT has positively impacted our everyday life, security and privacy mechanisms are essential since IoT networks and their devices deal with a huge amount of sensitive data. As a result, cryptographic protocols must be developed adequately, by taking into account the inherent features of such an environment. I will present some cryptographic solutions that were developed during my first postdoctoral contract, using modern cryptosystems (e.g., based on the discrete logarithm).

Nevertheless, the proposed cryptographic solutions rely on mathematical problems that will be solved by quantum computers. To prevent successful attacks by quantum computers, post-quantum cryptography (e.g., based on lattices) has been proposed. New quantum-resistant algorithms are on their way for standardisation. However, those algorithms bring extras (e.g., bigger component sizes, bigger calculations) that may impede the usability of post-quantum cryptography in our real world. In particular, with the limited resources of smart devices, IoT and post-quantum cryptography may not coexist. I will present some experimental results from implementing post-quantum algorithms in an IoT context, as a way to check the deployability of post-quantum cryptography in IoT.

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden’s revelation of mass-surveillance, PCS features in prominent messaging protocols such as Signal. In this talk, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols. We also apply the results obtained for this latter example in order to provide a quick fix, which massively improves its post-compromise security.

Consider the task of enumerating the answers to natural join queries over databases.
Given a join query, it is known that this can be done with ideal time guarantees (linear preprocessing and constant delay) iff the query is alpha-acyclic, under some fine-grained complexity assumptions. In the first part of the talk, we will inspect how the non-acyclic case can be handled, and in particular consider the affect of self-joins and endomorphisms in the query graph on the complexity. In the second part, we will consider more demanding query-answering tasks and see how to extend the requirements from the query structure beyond acyclicity to support these tasks efficiently.

We consider two-player zero-sum games with winning objectives beyond regular languages, expressed as a parity condition in conjunction with a Boolean combination of boundedness conditions on a finite set of counters which can be incremented, reset to $0$, but not tested. A boundedness condition requires that a given counter is bounded along the play. Such games are decidable, though with non-optimal complexity, by an encoding into the logic WMSO with the unbounded and path quantifiers, which is known to be decidable over infinite trees. Our objective is to give tight or tighter complexity results for particular classes of counter games with boundedness conditions, and study their strategy complexity. In particular, counter games with conjunction of boundedness conditions are easily seen to be equivalent to Streett games, so, they are CoNP-c. Moreover, finite-memory strategies suffice for Eve and memoryless strategies suffice for Adam. For counter games with a disjunction of boundedness conditions, we prove that they are in solvable in NP\cap CoNP, and in PTime if the parity condition is fixed. In that case memoryless strategies suffice for Eve while infinite memory strategies might be necessary for Adam. Finally, we consider an extension of those games with a max operation. In that case, the complexity increases: for conjunctions of boundedness conditions, counter games are EXPTIME-c.

In this talk, we present a work in progress about the complexity of proper colouring in hereditary classes of graphs. This problem, central in structural graph theory, is known to be NP-complete in the general case. We will focus on the colouring problem restricted to the classes of graphs defined by a set of forbidden induced subgraphs.
As Lozin and Malyshev recall in Vertex coloring of graphs with few obstructions, when the set H contains only graphs with 4 vertices there are only 3 remaining minimal classes of graphs for which the complexity of the colouring problem is still unknown. We study here one of these classes: the class of graphs containing neither cycles of size 4 nor stables of size 4, denoted by, Free{C4, 4K1}.
In (2P2, K4)-Free Graphs are 4-colorable, Gaspers and Huang showed that this class contains only graphs which can be covered by at most 4 cliques. According to the clique covering number, the problem shows different facets: easy if 2-cliques colourable, but harder otherwise.
We present here our partial results concerning the harder case. To tackle it, we use two complementary approaches: one theoretical, dealing with the concepts of clique-width, and one consisting in enumerating and recognising interesting structures using a computer program.
This talk could also mention enumerating graphs being the intersection of rectangles, if the audience wants to know about this.

This is a joint work with Cléophée Robin and Marco Caoduro