Hugo Férée (IRIF, Univ. Paris Diderot), Contributing to Higher Order Complexity: Outcomes and Likely Applications



Complexity theory has been mainly focused on computations over intrinsically finite objects like finite words, integers, trees and graphs, etc. In a broad sense, higher-order complexity deals with computations over more general domains and codomains, including real numbers, co-inductive datatypes or higher-order functions.

I will start by presenting a few results related to second-order complexity which motivated the main course of this talk: a proposition of definition for the complexity of higher-order functions based on game semantics. Finally, I will enumerate some potential applications and extensions of this work that I intend to pursue in the near future.