In this project we aim to study the foundations of processing large-scale, noisy string data. Our goal is to understand the limit of computations, and to provide new ultra-efficient algorithms and data structures for processing such data, inspired by approaches in hashing and high-dimensional geometry. We will focus on three research directions: streaming pattern matching, probabilistic text indexing, and sketching-based sting comparison. Algorithms and data structures on strings have traditionally been exploited in such fields as Bioinformatics, Information Retrieval, and Digital Security, and we expect our project to have a significant impact on these fields.

Directed graph (a.k.a. digraph) theory is a lot less developed than (undirected) graph theory and there is a lack of algorithmically meaningful structural theory for digraphs. The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs. Our methodology is two-fold. On the one hand, we will consider results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way. We will mainly focus on substructures in digraphs (complexity and conditions of existence) and extensions of graph colouring problems to digraphs. On the other hand, we will focus on the tools. We believe that many proof techniques have been too rarely used or adapted to digraphs and can be developed to obtain many more results. This in particular the case of median and cyclic order, the canonical decomposition of digraphs arising from matroids, the different notions of treewidth for digraphs, structural decomposition theorem, entropy compression and VC-deimension. Of course, those two approaches are not mutually exclusive but converge. Our goal is to develop the techniques to make advances in the above mentioned topics.

The main goal of this project is to explore the limits of tractability of computational problems in the quest of complexity dichotomies, especially in domains that have been weakly explored so far in the literature, and through the lens of parameterized complexity. I.e., our aim is to tackle problems for which a sharp distinction between the "easy" and "hard" cases is missing, for an appropriate definition of these terms. More precisely, we plan to focus our research on the following five tasks: (1) draw the line of efficiency among parameterized algorithms for forbidding structures in a graph (such as minors of induced subgraphs), (2) existence of polynomial kernels for structural parameterizations in the so-called ``distance from triviality'' framework, (3) obtaining complexity dichotomies for CSPs focusing on modification operations for various classes of structures, (4) optimality of algorithms using width parameters for dense graphs such as rank-width, and (5) devising efficient algorithms in directed graphs exploiting the notion of directed tree-width. While the scientific coordinator has extensively worked on some of these areas in the last years, most of the objectives of this project aim at tackling problems and research directions that have not been considered so far in the literature. To achieve these goals, the consortium is centered around the scientific coordinator, and its members are collaborators, from France and abroad (in Europe and other continents), which have been appropriately chosen to pursue this program.

Attacks exploiting micro-architectural vulnerabilities, such as Meltdown, Spectre, Rowhammer,etc., are on the rise. Modern day SoCs "System-on a Chips" embed increasingly complex design features, such as branchprediction, Out-of-Order execution, cache coherency protocols, integrated GPUs/FPGAs, new nonvolatile memories. The security aspect of these new architectures and technologies remains under-studied. This project aims at modeling the architectural problems with a virtual platform based on gem5. It will be used for penetration testing, evaluate the performance cost of countermeasures,anticipate new attacks and propose protections. These latter are validated on platforms based on ARMand RISC-V processors. The major impact of this project will be through the creation of a community around the virtual platform. The project will be carried out in collaboration with the SME Secure-IC,which will give industrial insights to the project.

Scheduling is a very wide topic in combinatorial optimization with applications ranging from production and manufacturing systems to transportation and logistics systems. Stated generally, the objective of scheduling is to allocate optimally scarce resources to activities over time. More specifically, given a set of jobs and a set of machines, scheduling optimization problems look for schedules s of the jobs on the machines that satisfy the side constraints and minimize the objective function f(s). We focus in this project on scheduling problems for which a schedule is completely characterized by the order in which the tasks are processed on the machines. For instance, we do not allow insertion of idle time between the processing of consecutive tasks. Various sources of uncertainty affect real scheduling problems, among which machine breakdowns, working environment changes, worker performance instabilities, tool quality variations and unavailability. Ignoring these uncertainties usually yields schedules that perform poorly under real conditions. Hence, researchers have introduced frameworks where the uncertainty is directly taken into account, either by considering random variables as input or in a worst-case approach where the uncertainty parameters are constrained in a set. These frameworks are respectively denoted by Stochastic Programming and Robust Optimization (RO). We disregard the former in this project because of its requirement for a probabilistic distribution of the random inputs, which is very difficult to obtain in practice. We focus instead on Robust Scheduling, which can be defined as follows. We are given uncertainty set U and we look for a schedule s that minimizes the objective function under the most adverse circumstance represented by U. Robust schedules are desirable from a practical perspective because they hedge against adverse conditions of the system. In spite of its practical relevance, robust scheduling has hardly become a practical tool since very simple scheduling problems become NP-hard as soon as U contains more than one scenario. This result is however not surprising because it is known that robust combinatorial optimization problems are, more often that not, harder than their deterministic counterpart. In this context, the positive results of Bertsimas and Sim (2003) opened a new avenue of research in robust combinatorial optimization. They introduced a new type of uncertainty set, denoted budgeted uncertainty, which keeps the complexity and approximability properties of the deterministic counterparts for robust combinatorial optimization that have a linear objective function and uncertain cost coefficients. Despite its practical relevance and its desirable computational properties, the budgeted uncertainty set has not yet been used in the robust scheduling literature. Our objective in this project is to start filling this gap: we will investigate combinatorial algorithms and integer programming formulations for robust scheduling problems with processing time uncertainty assuming that the processing times belong to that set. We expect that the resulting algorithms can turn budgeted robust scheduling into an efficient tool to handle processing time uncertainty.