Foto del docente

Ugo Dal Lago

Full Professor

Department of Computer Science and Engineering

Academic discipline: INF/01 Informatics


Keywords: Differential Program Semantics Quantum Computation Cryptography Automated Complexity Analysis

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.


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.


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 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.


Latest news

At the moment no news are available.