4 papers
Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations
Melissa Antonelli, Eduardo Skapinakis
This paper presents a high-level report on an ongoing project aiming to leverage implicit approaches based on discrete ordinary differential equations (ODEs) to study multiple comp…
Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
Melissa Antonelli, Arnaud Durand, Rui Li
The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a cons…
Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
Melissa Antonelli, Arnaud Durand, Juha Kontinen
Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. % fo…
Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
Melissa Antonelli, Arnaud Durand, Juha Kontinen
In this paper, we provide a uniform framework for investigating small circuit classes and bounds through the lens of ordinary differential equations (ODEs). Following an approach r…