Melissa Antonelli (Department of Computer Science – University of Helsinki) will lead a Philtech seminar titled
New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations.
The seminar will be held on September 18, 2025, 15:00 – 17:00 at Sala Martinetti – Via Festa del Perdono 7 – Milan.
Implicit computational complexity is an active area of theoretical computer science that aims to provide machine-independent characterizations of relevant complexity classes. One of the seminal works in this field emerged in the 1960s when Cobham introduced a function algebra closed under bounded recursion to capture polynomial-time computable functions (FP). Subsequently, several classes have been characterized using limited recursion schemas. An original proposal in this area was developed in 2019, relying on ordinary differential equations (ODEs). Initially introduced to capture FP, it has been recently generalized to the study of parallel computation. In the first part of the talk, we will briefly introduce the core concepts and motivations of implicit complexity and present the new ODE-based approach, highlighting its advantages for algorithmic design and for characterizing complexity classes. In the second part, we will focus on parallel complexity. After outlining the importance of these computational models, we will provide an overview of the main results obtained so far in capturing small circuit classes using ODE-based schemas and show how they offer a uniform framework for characterizing these classes.
Next seminars:
- September 25, 2025, 15:00 – 17:00 – On Probabilistic and Counting Computation: A Historical Overview.
- October 02, 2025, 15:00 – 17:00 – On counting propositional logic and Wagner’s hierarchy.
