Static complexity analysis aims at providing methods for determining how many computational resources (time units, memory cells) will be required by a program for its execution. Although this task subsumes, in general, a well known undecidable problem, it is possible to devise sound methods covering a large number of cases, including, if possible, those found in practice. The aim of the ELICA project is to develop logical methods for static complexity analysis, improve their expressiveness and extend their application to non-deterministic and concurrent programming paradigms. Logic-based tools, in particular of proof theoretic origin, have proved to be of capital importance for static complexity analysis. Criteria guaranteeing complexity bounds have been formulated (some by prospective participants to the ELICA project) using structural restrictions of the lambda-calculus, subsystems of linear logic in which cut-elimination has a limited complexity, type systems for functional languages, and semantic methods (polynomial interpretations and denotational semantics). These methods do not give precise bounds on the complexity of programs, but they have the advantage of being modular and of producing easily verifiable certificates. However, these methods currently apply only to a restricted range of programming languages, mostly of functional nature. Even in the functional case, the criteria are unsatisfactory in terms of expressiveness, i.e., with respect to the number of practical programs to which they can be applied. The ELICA project fixes as objective the development of extant logical methods and the introduction of new ones, in order to: - improve the expressiveness of static complexity analysis criteria for first-order functional languages, but above all extend the scope of such criteria to higher-order complexity (in particular, type-2 complexity), which is still largely unexplored; - increase the practical impact of these methods by defining complexity criteria for languages with imperative features, and relate them to the criteria for the verification of security properties (such as non-interference); - apply these methods to non-deterministic and probabilistic languages, to analyze the complexity of programs implementing randomized algorithms, with the long-term goal of employing such methods for the analysis of cryptographic and security protocols; - extend the scope of these methods to the analysis of concurrent systems. Here, the problem is above all of foundational nature, because there currently is no general definition of computational complexity for concurrent processes. We therefore propose to first develop a theory of computational complexity of interactive behaviors (generalizing problems and functions), capable of giving a formal content to notions such as answer time to a request, memory space, number of active processes, etc. Subsequently, we will study the application of logical methods to this theory.

Complex networks appear in many contexts: sociology, with friendship networks, collaboration networks, computer networks, with the Internet, the World Wide Web, blog networks, P2P networks, biology, with food webs, genetic regulatory networks, metabolic networks, epidemiology, energy and transportation with road networks, power grids, railways, airline routes, but also in economics, linguistics and many others. The emerging and promising domain of complex networks study, and in particular social ones, has proposed a stream of studies aimed at identifying properties of complex networks, their causes and consequences, describing their evolution and capturing everything into relevant models. These properties are used as key parameters in the study of various phenomena of interest like robustness, spreading of information, ideas or viruses. These questions are very transversal since diffusion phenomena can occur on many different social networks (including online ones) in the form of diseases, ideas, innovations, news or rumor, on computer networks with computer viruses which can propagate directly or by mail, p2p exchange systems, etc. Whether we consider the evolution of complex networks or the spreading of anything on them, we cannot expect it to be monotonic but rather to be composed of a background evolution with some specific events of prime interest. These events may correspond to abnormal activity on the network: for instance phone-call networks are over saturated for New Year's Eve, news blogs can be very reactive to specific events and in some occasion one per thousand to one percent of all blogs can talk about a given subject during one day (see today’s highlights on blogpulse.com for instance). Events can also be related to sudden changes in the network structure, e.g. routing tables updates after a link failure. Being able to detect or predict such events is of key interest. The CODDDE project aims at studying critical research issues in the field of real-world complex networks study: - How do these networks evolve over time? - How does information spread on these networks? - How can we detect and predict unexpected changes in their structure? In order to answer these questions, an essential feature of complex networks will be exploited: the existence of a community structure among nodes of these networks. Complex networks are indeed composed of internally densely connected groups that have few interactions with one another. The CODDE project will therefore propose new community detection algorithms to reflect complex networks evolution, in particular with regards to diffusion phenomena and anomaly detection. These algorithms and methodology will be applied and validated on a real-world online social network consisting of more than 10 000 blogs and French media collected since 2009 on a daily basis (the dataset comprises all published articles and the links between these articles) correlated with a twitter dataset. The consortium of the project comprises two academic partners from large research labs, with a strong experience in complex networks: the Complex Networks team from LIP6-UPMC (Laboratoire d’Informatique de Paris 6 of Université Pierre et Marie Curie), and the LIP-ENS Lyon team (Laboratoire d’Informatique du Parallélisme of the École Normale Supérieure de Lyon), and one industrial partner: the Linkfluence SME, who will be in charge of data collection. Moreover, the expertise of Linkfluence blogs analysts will be used during the results validation phase.

DyVerSe aims to develop a theoretical framework for dynamic/game semantics for programming languages, capturing in one versatile setting a spectrum of computational features, representative of the heterogeneity of software (e.g. higher-order functions, concurrency, probabilities or other quantitative aspects). Our ambition is (1) to help unify denotational semantics by providing the missing link between various incompatible models focusing on specific aspects, and (2) to provide a toolbox to reason compositionally about the dynamic behaviour of programs, with an eye towards specification and verification. Operational semantics is a powerful and extensible methodology, perfectly fit for formalization; on the other hand its deployment often follows from ad-hoc choices. It is tied to syntax and struggles with compositionality. Denotational semantics is syntax-independent, and often more principled. It is a great tool to reason about program equivalence or to prove general properties of languages and inform language design, and it comes with compositional reasoning principles on programs. In exchange, it is more mathematically demanding and it is often quite brittle: distinct fragments of the same language may require radically different representations. Denotational models often concern specific programming features, they are are not usually easily extended or combined. DyVerSe seeks to provide the missing link between the syntax-tied operational semantics and a spectrum of incomparable denotational semantics of restricted scope: a syntax-independent and fine-grained description of program executions which could serve both as a unified compositional operational semantics for a wide array of computing features, and as a bridge between specific denotational models. Besides constructing this missing link, DyVerSe aims to put it to work in order to obtain reasoning principles on high-level effectful programs, permit model extraction for automated program verification, or help put under scrutiny the structures used to eliminate race conditions and ensure harmonious use of resources in languages like Rust (among others). To achieve that, DyVerSe builds on recent developments in Game Semantics. Game semantics departs from mainstream denotational semantics by representing the interactive behaviour of programs rather than merely input/output. It is famous for managing to accommodate multiple programming features (various degrees of state, control operators, evaluation order) in one single unified canvas, for sequential deterministic programs; an achievement which has had a strong impact on semantics and beyond, and for which the founders of game semantics were recently awarded the Alonzo Church Award. Though there are games model beyond the sequential deterministic setting, they are incomparable and do not fit in a unified picture anymore. To that defect, recent work on non-deterministic and probabilistic game semantics propose the diagnosis that traditional game semantics lack the required structure to explicitly represent various branching behaviour (such as parallelism, non-determinism, probabilistic choice). To provide this missing branching structure, we propose to build on Concurrent/Asynchronous games. Concurrent games are a branch of game semantics focusing on representing the causal choices behind program actions rather than merely their observations by execution environments. Pioneered by Abramsky and Melliès, they have recently been actively developed building on new definitions due to Winskel, and are finally catching up in expressivity with traditional models. In DyVerSe we will push the development of concurrent games -- their structure, their use for semantics of combinations of effects, their relationship with operational semantics -- to provide the missing link, and put these structures to work towards better tools to reason on or verify programs.

Given one or more geometric shapes (tiles), it seems natural to wonder whether they can tile the plane or not - with no overlap or gap. More precisely and in ascending order of complexity, we may wonder if the set of tiles can tile the whole plane; if it can do so in a periodic way; and how many different tilings exist. These three problems, formulated for a combinatoric version of tilings, tilings by Wang tiles, have proven to be highly difficult. This kind of tilings - also called subshifts of finite type (SFT) - are sets of colourings of the infinite grid that respect a finite number of local constraints. They can fruitfully be seen as a computational model since they can be used to encode Turing machine computations, as well as a discrete model for dynamical systems, which is the point of view of symbolic dynamics. This model has been adapted to the hyperbolic plane and to trees, but we can go further and generalize it: the infinite grid is seen as the group Z², and this group is replaced by any finitely generated group. This new point of view has two advantages: first, it unifies previous examples and will lead to results not specific to one group. Second, it defines a worthwhile computational model, relatively unexplored until now: subshifts on groups. For computer scientists, mathematical notions based on group theory provide a new and deeper understanding of subshifts as computational model. On the other hand, this computer science approach offers an innovative point of view on groups that will interest mathematicians, for instance by providing new invariants. All this perfectly illustrates how mathematics and theoretical computer science can benefit from each other. This project focuses on the three aforementioned challenges, and explores which dynamical, combinatorial or geometric properties of the group control the computational and combinatorial properties of the subshifts it defines. First, it is noteworthy that the question of the existence of a colouring - emptiness problem - for SFTs is decidable on Z, whereas it becomes undecidable on Z². But can we characterize groups having a decidable emptiness problem? The second question concerns aperiodic subshifts - subshifts in which no colouring is left invariant by a translation. On Z, SFTs are too simple objects to produce only aperiodic configurations, while Z² does admit aperiodic SFTs. But for which groups can SFTs force aperiodicity? The third question concerns entropy, i.e. the growth rate of patterns of size n that appear in the subshift. Computing this entropy is easy for SFTs on Z, but entropy function is uncomputable for SFTs on Z². Even if we override the uncomputability of the function and focus on particular examples of SFTs, computing the entropy remains a difficult task. Indeed, a closed formula for entropy is known only for a few simple SFTs on Z². Can we compute the exact value of entropy of other 2D SFTs, and give sharp approximations on the entropy of SFTs on Z²? In the last ten years, the introduction of tools from computability theory, and more precisely the use of subshifts as computational models, has proven highly efficient by providing a solution to long-standing problems in symbolic dynamics. Even more recently, the international community of symbolic dynamicists, who traditionally focused on the cases of Z and Z² - and to a much lesser extent on the hyperbolic plane and on trees - has started to get interested in the case of finitely generated groups, as a way of unifying the previous examples. The writing of this project follows several new results, in which the members of the project have actively participated. Three of these members are specialized in symbolic dynamics - Nathalie Aubrun, Michael Rao and Jarkko Kari - and are internationally recognized for their expertise on computability issues, combinatorics on words and computer-aided proofs. The requested funding will help bolster their leading position at an international level.

High performance computing (HPC) allows scientists and industries to run large numerical application on huge data volumes. The HPC is a key factor in knowledge and innovation in many fields of industry and service, with high economic and social issues: aerospace, finance and business intelligence, energy and environment, chemicals and materials, medicine and biology , digital art and games, Web and social networks, ... Today, acquiring HPC supercomputer is very expensive, making HPC unreachable to SMIs / SMEs for their research and development. The CloudPower project results from the research and development projectXtremWeb lead INRIA, CNRS, University Paris XI and ENS Lyon. Its goal is to offer a low cost Cloud HPC service for small and medium-sized innovative companies. With CloudPower, companies and scientists will run their simulations to design and develop new products on a powerful, scalable, economical, reliable and secure infrastructure. The project will lead the creation of a new and innovative company operating the platform implemented in the framework of the ANR Emergence. CloudPower will leverage on the open-source software XtremWeb-HEP previously developed by the partners. The principle of the technology is to collect the under-exploited resources on the Internet (individual PCs, internet box, servers, data centers ...) to build a virtual supercomputer providing HPC services on demand. CloudPower will implement SaaS / PaaS portal for customers and develop extensions to allow commercial exploitation of unused resources. Building on the network of SMIs from the competitiveness clusters System@tic and LyonBiopole, we will implement scenarios and/or demonstrators which illustrate the ability of CloudPower to increase competitiveness, research and marketing of innovative SMEs.