Thomas Seiller - ReACT

ReACT Project

H2020

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".

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.

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