12 citations · 21 across the 8 of their papers we have counts for
4 papers · 1 filter
Realizing Implicit Computational Complexity
Clément Aubert, Thomas Rubiano, Neea Rusch +1
This abstract aims at presenting an ongoing effort to apply a novel typing mechanism stemming from Implicit Computational Complexity (ICC), that tracks dependencies between variabl…
Lower bounds for algebraic machines, semantically
Luc Pellissier, Thomas Seiller
This paper presents a new semantic method for proving lower bounds in computational complexity. We use it to prove that maxflow, a PTIME complete problem, is not computable in poly…
Probabilistic Complexity Classes through Semantics
Thomas Seiller
In a recent paper, the author has shown how Interaction Graphs models for linear logic can be used to obtain implicit characterisations of non-deterministic complexity classes. In…
Proceedings Third Joint Workshop on Developments in Implicit Computational complExity and Foundational & Practical Aspects of Resource Analysis
Thomas Seiller, Steffen Jost
These proceedings present the accepted regular papers and some selected extended abstracts from the 3rd joint DICE-FOPARA workshop, which was held in Prague, Czech Republic on Apri…