ReACT Project

I submitted in September 2014 an application for a Marie Curie Individual Fellowship (call H2020-MSCA-IF-2014, Mathematics (MAT) Panel) which was successful. This project, ReACT (A Realizability Approach to Complexity Theory, grant agreement No 659920) funds a two-year research stay to work with Jakob Grue Simonsen at the Computer Science department of the University of Copenhagen (DIKU). It is part of the European Union's Horizon 2020 program for research and innovation. A (largely) expanded version of the associated research project, along with an exposition of first results, can be found in the preprint "Towards a Complexity-through-Realizability Theory".

Project Summary

Complexity theory concerns fundamental questions on the mathematics of computer science about the amount of resources needed to run programs or solve problems. The ReACT project will build on recent work in realizability models for linear logic to provide new characterizations of existing complexity classes. The end goal is to enable researchers to attack long-standing open problems in complexity theory by using mathematical techniques, tools and invariants from operators algebras and dynamical systems. The "complexity-through-realizability" techniques developed by the ReACT project will provide a unified framework for studying many computational paradigms and their associated computational complexity theory grounded on well-studied mathematical concepts. This will allow for comparison of complexity classes defined from different computational paradigms (e.g. sequential and quantum computation), as well as establish a theory of complexity for computational paradigms lacking such (e.g. concurrent processes).
The "complexity-through-realizability" approach stems from established logical-based approaches of complexity theory and inherits their strengths. It furthermore improves crucially over them as it builds upon state-of-the-art theoretical results on realizability models for linear logic using well- studied mathematical concepts from operators algebras and dynamical systems. As a consequence, it opens the way to the use against the open problems of the discipline the many techniques, tools and invariants that were developed in these mathematical disciplines.
The ReACT project has two objectives. The first objective aims at establishing this new approach to complexity as an emerging and promising field of study which generalises and extends previous techniques. The second objective is to investigate investigating how the mathematical methods and techniques derived from of our approach can be used to attack long-standing open problems in complexity theory.

Related Events: DICE 2016

I am in the program committee of the 2016 edition of DICE (Developments in Implicit Computational complExity), an ETAPS workshop. Don't hesitate to submit via easychair (deadline January 31st, 2016).

Documents

I will provide here links to documents related to the project. This includes publications, preprints and any other document exposing the results obtained so far. I also provide, at the bottom of the page, the documents related to my application for a Marie Curie fellowship, namely Part B of the proposal (this is the main part of the proposal as part A contains only administrative informations) and the evaluation report.

Publications and Preprints

Interaction Graphs: Nondeterministic Automata, February 2016.

pdf Abstract Bibtex

This paper exhibits a series of semantic characterisations of sublinear nondeterministic complexity classes. These results fall into the general domain of logic-based approaches to complexity theory and so-called implicit computational complexity (ICC), i.e. descriptions of complexity classes without reference to specific machine models. In particular, it relates strongly to ICC results based on linear logic since the semantic framework considered stems from work on the latter. Moreover, the obtained characterisations are of a geometric nature: each class is characterised by a specific action of a group by measure-preserving maps.

@unpublished{seiller-IGNDA,
Author = {Seiller, Thomas},
Title = {Interaction Graphs: Nondeterministic Automata},
Note = {submitted},
Year = {2016},
}

Towards a Complexity-through-Realizability Theory, January 2015.

pdf Abstract Bibtex

We explain how recent developments in the fields of realizability models for linear logic -- or geometry of interaction -- and implicit computational complexity can lead to a new approach of computational complexity. This semantic-based approach should apply uniformly to various computational paradigms, and enable the use of new mathematical methods and tools to attack problem in computational complexity. This paper provides the background, motivations and perspectives of this complexity-through-realizability theory to be developed, and illustrates it with recent results.

@article{seiller-towards,
Author = {Seiller, Thomas},
Title = {Towards a Complexity-through-Realizability Theory},
Journal = {submitted},
Year = {2015},
}

Measurable Preorders and Complexity, Abstract for TACL 2015.

pdf Abstract Bibtex

In a recent paper, we defined a generic construction of models of the exponential-free fragment of Linear Logic (MALL). These models provide a new framework for the study of computational complexity which allows for the use of techniques and invariants form ergodic theory and operator theory.

@unpublished{seiller-tacl2015,
Author = {Seiller, Thomas},
Title = {Measurable Preorders and Complexity},
Note = {Abstract},
Year = {2015},
}

Interaction Graphs and Computational Complexity I, in preparation.

(Draft) Abstract Bibtex

The aim of Implicit Computational Complexity is to study algorithmic complexity only in terms of restrictions of languages and computational principles. Based on previous work about realizability models for linear logic, we propose a new approach where we consider semantical restrictions instead of syntactical ones. This leads to a hierarchy of models mirroring subtle distinctions about computational principles. As an illustration of the method, we explain how to obtain characterizations of infinite families of complexity classes lying in between the set of regular languages (resp. stochastic languages) and the sets of (deterministic and non-deterministic) logarithmic space predicates (resp. probabilistic logarithmic space predicates).

@unpublished{seiller-IGCompI,
Author = {Seiller, Thomas},
Title = {Interaction Graphs and Computational Complexity {I}},
Note = {in preparation},
Year = {2015},
}

Interaction Graphs and Computational Complexity II, in preparation.

pdf Abstract Bibtex

This paper is a second work concerned with a new approach of computational complexity under the vantage point offered by the theory of interaction graphs. In this paper, we use intuitions gained from the recent study of constrained exponential connectives in interaction graphs to exhibit a monoid of measurable maps such that the associated deterministic GoI model characterizes the class P of polynomial time predicates. We also study the corresponding non-deterministic model and the complexity class it characterizes.

@unpublished{seiller-IGCompII,
Author = {Seiller, Thomas},
Title = {Interaction Graphs and Computational Complexity {II}},
Note = {in preparation},
Year = {2015},
}

Slides

Measurable Preorders and Complexity, TACL2015, June 26th 2015, Ischia Porto (IT)pdf

Towards a Complexity-through-Realizability Theory, FOPARA/DICE, ETAPS Workshop, April 12th 2015, Londres (UK)pdf

A realisability approach to complexity theory, HCC seminar, November 27th 2015, University of Copenhagen (Denmark)pdf

Application Documents

Part B of the Application for the ReACT project. pdf

Evaluation Report for the ReACT project. pdf

2008 Seiller Thomas