SCOT: A Seminar on Semantic and Formal Approaches to Complexity
The SCOT Seminar is devoted to the problem of reasoning on the complexity of programs
in formal and compositional ways. Many approaches have been exploited for that, taking
advantage from logic, category theory, denotational semantics, type systems, interpretations, etc.
This seminar aims at providing a forum of discussion for all issues related to these questions,
from foundational aspects on semantics of complexity to automated time or space complexity
The seminar is held
List of Seminars
- On a monthly basis
Tuesday, March 23rd 2021, 3:00pm to 4:00pm (CET)
Olivier Bournez. Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations.
We will talk about the expressive and computational power of discrete Ordinary
Differential Equations (ODEs), a.k.a. (Ordinary) Difference Equations. We present a new
framework using these equations as a central tool for computation and algorithm design.
We present the general theory of discrete ODEs for computation theory, and we will
illustrate this with various examples of algorithms, and we provide several implicit
characterizations of complexity and computability classes. The proposed framework
presents an original point of view on complexity and computation classes. It unifies
several constructions that have been proposed for characterizing these classes including
classical approaches in implicit complexity using restricted recursion schemes, as well
as recent characterizations of computability and complexity by classes of continuous
ordinary differential equations. It also helps understanding the relationships between
analog computations and classical discrete models of computation theory. At a more
technical point of view, this work points out the fundamental role of linear (discrete)
ODEs and classical ODE tools such as changes of variables to capture computability
and complexity measures, or as a tool for programming many algorithms. This is joint
work with Arnaud Durand.
Tuesday, April 13th 2021, 3:00pm to 4:00pm (CET)
Cynthia Kop. Tuple Interpretations for Higher-Order Complexity.
A lot of work has been done in the study of complexity of first-order term
rewriting systems. However, for higher-order term rewriting, techniques for complexity
analysis are sparse. In this presentation, we will discuss a method based on
interpretations. By mapping all base-type terms to tuples of integers, and terms of a
higher type to functions over tuples, we obtain a powerful technique that not only can be
used to assess runtime complexity, but may also offer some first steps towards a native
complexity notion for higher-order systems.
Tuesday, May 18th 2021, 3:00pm to 4:00pm (CET)
Georg Moser. Automated Analysis of Splaying et al.
Being able to argue about the performance of self-adjusting data structures such as
splay trees has been a main objective, when Sleator and Tarjan introduced the notion
of *amortised* complexity. Analysing these data structures requires sophisticated
potential functions, which typically contain logarithmic expressions. Possibly for
these reasons, and despite the recent progress in automated resource analysis,
they have so far eluded automation. In this talk, I will report on the first
fully-automated amortised complexity analysis of self-adjusting data structures
and the underlying theory. Following earlier work, the analysis is based on
potential function templates with unknown coefficients. This is joint work
with Lorenz Leutgeb, David Obwaller and Florian Zuleger.
Tuesday, June 22nd 2021, 3:00pm to 4:00pm (CET)