Calendrier des animations scientifiques

Fully Homomorphic Encryption allows evaluating an arbitrary function over encrypted data while preserving the privacy of the messages. This property has found numerous applications especially in the case where one would like to process data stored in the cloud in a private way. In this talk, I will focus on the privacy of the algorithm processed by the cloud. Fully Homomorphic Encryption sanitization guarantees that all the information about how a ciphertext has been obtained is destroyed, except the associated message. In particular, it is impossible to say which computation has been processed in order to obtain a sanitized ciphertext, even knowing the secret key. We will see how to build a sanitization algorithm from the TFHE bootstrapping (Asiacrypt 2016) and how it compares to the previous soak-and-spin strategy proposed by Ducas and Stehlé (Eurocrypt 2016).

This is joint work with Florian Bourse.

Prenons un graphe non orienté. Il peut représenter les routes d’une ville, la couverture d’un territoire par des capteurs, ou même les relations entre des individus. Si nous voulons installer des caméras à des intersections pour surveiller toutes les routes, il existe une solution simple, en mettre à chaque intersection. Si nous voulons éviter d’utiliser deux capteurs côtes-à-côtes pour surveiller un territoire, il existe une solution simple, choisir les capteurs un par un en oubliant tous les voisins. Si nous voulons un ensemble d’individus qui ne se connaissent pas, qui sont en relation avec tous les autres, mais que nous ne pouvons choisir que par grappes, existe-t-il toujours une solution simple ? D’un point de vue théorique, ce problème est celui de l’Indépendant Dominant avec des Obligations. Nous verrons que déterminer l’existence d’une solution devient particulièrement difficile, en particulier que ce problème est NP-complet même dans un chemin. Pour saisir la place des obligations dans ce saut de complexité, nous nous pencherons également sur son impact dans des problèmes de tournées.

Workload equity is an emerging topic in the routing literature. Typically, efficient solutions usually lack equity, thus, the challenge is to propose models and algorithms capable of finding solutions with an equitable workload distribution between drivers with a low impact on the routing cost. In the current literature, most papers naturally manage equity within a bi-objective model. In this work, we rather use the classic min cost objective as the single objective and manage equity on the drivers route costs with equity constraints. We use a test-bed routing problem motivated by the non-emergency transportation of patients integrating our equity constraints. We show that the straightforward set partitioning formulation can not be solved efficiently by a standard branch-and-price approach and propose three original solution methods, two branch-and-price algorithms and a heuristic. The proposed branch-and-price algorithms are based on new models to manage the equity constraints. In the first model, the variables (columns) are indexed by a route and a driver. In the second model, equity constraints are expressed on nodes instead of drivers. The heuristic is based on a dichotomic search. Algorithms are evaluated on real world based instances with up to 50 customers. Computational experiments highlight pros and cons of each algorithm and show that equitable solutions can be found with low impact on the routing cost.

Many important polynomial systems have additional structure, for
example, generating polynomials invariant under the action of the
symmetric group. In this talk we consider two questions for such
systems. The first focuses on computing the critical points of a
polynomial map restricted to an algebraic variety, a problem which
appears in many application areas including polynomial optimization
and real algebraic geometry. Our second problem is to decide the
emptiness of algebraic varieties over real fields, a starting point
for many computations in real algebraic geometry. In both cases we
provide efficient probabilistic algorithms which take advantage of
the special invariant structure. In particular in both instances our
algorithms obtain their efficiency by reducing the computations to
ones over the symmetric group orbits and make use of tools such as
weighted polynomial domains and symbolic homotopy methods.

This contains joint works with J.-C. Faugère, G. Labahn,
C. Riener, M. Safey El Din and É. Schost.

The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres, closed manifolds and finite graphs without endpoints : if a set X is homeomorphic to a sphere, a closed manifold or a such graph, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović and others in the recent years.

We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs.