1 citations · 2 across the 9 of their papers we have counts for
11 papers
(Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography
Ugo Dal Lago, Giulia Giusti
In this paper, we show how a recently introduced -calculus for randomized computation, called , can accurately capture the notions of first- and second-order poly…
Coinductive reasoning for parametrized functors and monads
Ugo Dal Lago, Zeinab Galal
Lax extensions (also called relators or relation liftings) are a categorical notion to reason about functors acting on functions and relations in a compatible way. They play a cent…
When Types Intersect and Effects Get Handled
Stefano Catozi, Ugo Dal Lago, Taro Sekiyama
We introduce a novel intersection type system for a -calculus with algebraic effects and handlers. The system, inherently behavioral in nature, enjoys the classical properties o…
Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
Andrea Colledan, Ugo Dal Lago
We introduce a type system for the Quipper language designed to derive upper bounds on the size of the circuits produced by the typed program. This size can be measured according t…
On Computational Indistinguishability and Logical Relations
Ugo Dal Lago, Zeinab Galal, Giulia Giusti
A -calculus is introduced in which all programs can be evaluated in probabilistic polynomial time and in which there is sufficient structure to represent sequential cryptographi…
On Separation Logic, Computational Independence, and Pseudorandomness (Extended Version)
Ugo Dal Lago, Davide Davoli, Bruce M. Kapron
Separation logic is a substructural logic which has proved to have numerous and fruitful applications to the verification of programs working on dynamic data structures. Recently,…
A Characterization of Basic Feasible Functionals Through Higher-Order Rewriting and Tuple Interpretations
Patrick Baillot, Ugo Dal Lago, Cynthia Kop +1
The class of type-two basic feasible functionals () is the analogue of (polynomial time functions) for type-2 functionals, that is, functionals that c…
Circuit Width Estimation via Effect Typing and Linear Dependency (Long Version)
Andrea Colledan, Ugo Dal Lago
Circuit description languages are a class of quantum programming languages in which programs are classical and produce a description of a quantum computation, in the form of a quan…
On Feller Continuity and Full Abstraction (Long Version)
Gilles Barthe, Raphaëlle Crubillé, Ugo Dal Lago +1
We study the nature of applicative bisimilarity in -calculi endowed with operators for sampling from continuous distributions. On the one hand, we show that bisimilarity, logica…
Multi types and reasonable space
Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni
Accattoli, Dal Lago, and Vanoni have recently proved that the space used by the Space KAM, a variant of the Krivine abstract machine, is a reasonable space cost model for the lambd…
Proceedings Second Joint International Workshop on Linearity & Trends in Linear Logic and Applications
Ugo Dal Lago, Valeria de Paiva
This volume contains a selection of papers presented at Linearity&TLLA 2020, namely the Second Joint International Workshop on Linearity & Trends in Linear Logic and Applications,…