Ugo Dal Lago's research area is theoretical computer science. In particular, he is interested in relations between computational complexity theory, probability theory, programming language theory and mathematical logic.
PROBABILISTIC HIGHER-ORDER COMPUTATION
Even if algorithms are traditionally considered as deterministic processes, the possibility for algorithms to access sources of randomness has been taken into account since the birth of theoretical computer science. This is not only convenient, but necessary in cryptography, while probabilistic models are among the most successful approaches to machine learning. A lot of questions remain however open, despite the huge literature on the subject. In particular, the impart of adopting a probabilistic model of computation to the theory of programming languages is largely unexplored, in particular when higher-order functions are available.
DIFFERENTIAL SEMANTICS OF PROGRAMMING LANGUAGES
The semantics of programming languages is historically studied through equivalences and preorders on programs, which do not give any quantitative information about pairs of programs that are not comparable. The use of metrics and pseudometrics, although promising, does not account for differences between programs that depend in on the context. We are therefore trying, through notions of distance between programs that are not merely numerical, to be able to justify certain extremely interesting transformations between programs.
IMPLICIT COMPUTATIONAL COMPLEXITY
Implicit computational complexity aims at giving characterizations of complexity classes based on mathematical logic. Starting from Linear Logic, one could define deductive systems which correspond to complexity classes as soon as cut-elimination is interpreted as the underlying computational mechanism. In particular, characterizations of polinomial and elementary time functions have been introduces by Girard and Lafont in the last ten years. These proposals are interesting both from the point of view of computational complexity and from the point of view of programming language theory.
