DIENS

In this talk I will attempt to answer the following questions I have been asked quite often: What are the current challenges in dynamic graph algorithms? What are good starting points for people who want to try working in this field? The talk will focus on challenges for basic graph problems (e.g. connectivity, shortest paths, maximum matching), and will survey some existing upper and lower bound results and techniques.

In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines.

A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction.

In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

The idea of Probabilistic Programming is to use the expressiveness of programming languages to build probabilistic models. To implement this idea, a common approach is to take a general purpose language and extend it with (1) a function that allows to sample a value from a distribution, (2) a function that allows to condition values of variables in a program via observations, and (3) an inference procedure that build a distribution for a program using the two previous constructs.

Following this approach, we propose to extends a reactive programming language with probabilistic constructs. This new language enables the modeling of probabilistic reactive systems, that is, probabilistic models in constant interaction with their environment. Examples of such systems include time-series prediction, agent-based systems, or infrastructure self-tuning.

To demonstrate this approach, we started from ReactiveML, a reactive extension of OCaml that supports parallel composition of processes, communication through signals, preemption, and suspension. We extend the language with classic probabilistic constructs (sample, factor la WebPPL) and propose an inference scheme for reactive processes, that are, non-terminating functions.

This is a join work with Guillaume Baudart, Martin Hirzel, Kiran Kate, and Avraham Shinnar.

Working on various industrial case-studies in the past decade, we realized that, given the very quick evolution of hardware platforms, and the growing complexity of embedded software, it is, more than ever, necessary to start with a very general point of view. On one hand we need to understand the physical timing constraints and tolerances as determined by control engineers for a given application (sampling frequencies and jitters, end-to_end latencies, etc.), without mentioning software entities like tasks or scheduling. On the other hand we need to characterize precisely the computation and communication performances of a given execution platform, and assess their predictability. Designing the implementation means finding space and time allocations for the application functional parts, in such a way that the physical constraints are met by construction, and in a provable way for certification authorities. We will use examples with the Kalray MPPA, to illustrate the nature and specification of the timing constraints, the implementation schemes, and how the constraints can be met.

“Big mechanisms are large, explanatory models of complicated systems in which interactions have important causal effects. The collection of big data is increasingly automated, but the creation of big mechanisms remains a human endeavor made increasingly difficult by the fragmentation and distribution of knowledge. To the extent that the construction of big mechanisms can be automated, it could change how science is done”. Paul Cohen, DARPA 2014.
If biological big data has underlying “big mechanisms”, there is little hope that any mental construction can ever comprehend these “large explanatory models”. Moreover, because of the combinatorics of protein-protein interactions, no static map, database, or ontology list, can suffice to complement human brains in the design of these models. These simple observations have taken a large swath of molecular biologists away from any (formal or semi-formal) modeling activity. Most experimental biologists give little credit to existing models, which they know are partial, outdated and have little predictive power. Yet, while rejecting models, experimental biologists have to rely on implicit mental constructs in order to decide which experiment to set up. Thus every biologist has a model, either implicitly or explicitly. In this presentation, we argue that the lack of success story of formal models in Systems biology is not due to the impossibility of having accurate and u! seful models, but rather to the fact that one is confusing models of interactions with explanations of biological functions. Our approach is to view models as programs and biological functions as computations. If models are to be treated as programs what language one should use to assemble them is a critical point. In this talk we will present the issue of modeling biological "big mechanisms": i.e, protein-protein interaction networks whose specification is too combinatorial to be explicitly represented. In particular we will discuss the lessons that can be learned from the DARPA "BIGMEC" project, in which we took part, and that involved conjuncts efforts from A.I experts, biologists and language theory computer scientists.