Mathematical Informatics

Traditional computability theory does not fully capture the essence of computation. It focuses on what can be computed, neglecting how things are computed. I will present a mathematization of computer science fundamental notions, grounded in the theory of dynamical systems, which prioritizes the ‘how’ over the ‘what’. This approach has numerous implications, enabling:

  1. A uniform account of existing lower bounds, and new lower bound results, in algebraic complexity
  2. Static analysis methods which can be implemented in usable tools
  3. The definition of new dynamical models of linear logic
  4. New perspectives on implicit computational complexity and the formal definition of the notion of algorithm

In this talk, I will focus on two applications:

  • discretizing abstract programs for static analysis (related to 2. and 4.)
  • extracting mathematical structure from corpora to understand large language models (related to 3. and 4.)