Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

1 avril 2019

TBA

Meghyn Bienvenu (LABRI)

TBA

25 mars 2019

TBA

Etienne Moutot (ENS-Lyon)

TBA

18 mars 2019

TBA

Sébastien Labbé (LABRI - Université de Bordeaux)

TBA

18 février 2019

The power of programs over monoids taken from some small varieties of finite monoids

Nathan Grosshans (ENS)

The computational model of programs over monoids, introduced by Barrington and Thérien in the late 1980s, gives a way to generalise the notion of (classical) recognition through morphisms into monoids in such a way that almost all open questions about the internal structure of the complexity class NC^1 can be reformulated as understanding what languages (and, in fact, even regular languages) can be program-recognised by monoids taken from some given variety of finite monoids. Unfortunately, for the moment, this finite semigroup theoretical approach did not help to prove any new result about the internal structure of NC^1 and, even worse, any attempt to reprove well-known results about this internal structure (like the fact that the language of words over the binary alphabet containing a number of 1s not divisible by some fixed integer greater than 1 is not in AC^0) using techniques stemming from algebraic automata theory failed.
In this talk, I shall present the model of programs over monoids, explain how it relates to “small” circuit complexity classes and present some of the contributions I made during my Ph.D. thesis to the understanding of the computational power of programs over monoids, focusing on the well-known varieties of finite monoids DA and J (giving rise to “small” circuit complexity classes well within AC^0). I shall conclude with a word about ongoing work and future research directions.

11 février 2019

Two-Way Parikh Automata with a Visibly Pushdown Stack

Luc Dartois (LACL UPEC)

In this talk we investigate the complexity of the emptiness problem for Parikh automata equipped with a pushdown stack.
Pushdown Parikh automata extend pushdown automata with counters which can only be incremented and an acceptance condition given as a semi-linear set, which we represent as an existential Presburger formula over the final values of the counters. The non-emptiness problem both in the deterministic and non-deterministic cases is NP-c. If the input head can move in a two-way fashion, emptiness gets undecidable, even if the automaton deterministic.
We shift our focus to Visibly Pushdown Automata (read automata on XML documents) and we recover decidability using the single-use syntactic restriction, enforcing that any transition which increments at least one dimension is triggered only a bounded number of times per input position.
The main result showed in this talk is that non-emptiness of two-way visibly Parikh automata which are single-use is NExpTime-c.
We finally give applications of this result to decision problems for expressive transducer models from nested words (again read XML documents) to words, including the equivalence problem.

4 février 2019

Bornes inférieures dans les circuits arithmétiques : un focus sur la profondeur constante

Sébastien Tavenas (LAMA - Université de Savoie)

Le problème “P=NP?” est largement reconnu comme le principal problème ouvert en informatique théorique. Étant donné la difficulté de ce problème, des versions algébriques, un peu plus faibles, ont été définies. On espère alors que des méthodes géométriques ou algébriques seront plus faciles à appliquer. On s’intéressera à une version “VP=VNP?” proposée par Leslie Valiant à la fin des années 70 où on étudie la complexité de l’évaluation des polynômes. Le contenu algorithmique de ce problème peut être résumé en une phrase : est-il possible d’évaluer le permanent d’une matrice n*n en un nombre d’opérations arithmétiques polynomial en n ?
On présentera ce problème, puis on s’intéressera plus particulièrement à une de ses caractéristiques (connue depuis 1983) qui le différencie de son homologue Booléen : tout polynôme qui est efficacement calculable est aussi efficacement parallélisable. Ainsi, pour obtenir des bornes inférieures dans le cas général, il est suffisant de trouver des bornes “assez bonnes” en petite profondeur. On finira alors par exhiber des bornes inférieures (malheureusement insuffisantes pour résoudre VP=VNP) en profondeur 3 et 4.

28 janvier 2019

Points apériodiques dans les sous-shifts de dimension 2

Anael Grandjean (LACL UPEC)

La théorie des espaces de pavages (sous-shifts) a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au coeur de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en dimension 2 :

Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ?
Comment se comportent les espaces de pavages ne possédant aucun point apériodique ?

Nous montrons qu’un espace de pavage 2D sans point apériodique a une structure très forte : il est “équivalent” (presque conjugué) à un espace de pavage 1D, et ce résultat s’applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s’appliquent aux espaces 2D sans point apériodique. La situation en dimension supérieure semble beaucoup moins claire.

Cet exposé est issu d’une collaboration avec Benjamin Hellouin de Menibus et Pascal Vanier

7 janvier 2019

The Automotive Analytics Factory as a Big Data Concept

Daniel NEAGU (Daniel NEAGU)

Big data is currently the new commodity empowering Industry 4.0 towards an effective digital economy.
Current developments in data gathering using sensors and data-driven technologies connected through the Internet of Things enable automotive industry among others to join the efforts to process data into information with the aim to extract knowledge and generate intelligent actions. For example the automotive industry invests in big data systems from the car lifecycle, including product development and vehicles in the field to R&D. Consequently the
demand for effective big data processes increases, with challenges derived from both scarcity of effective tools and expertise to issues regarding data quality and model management.
This talk reviews the journey of the Advanced Automotive Analytics (AAA) team at the University of Bradford, with details and examples of recent and current contributions. The team’s vision of the Automotive Analytics Factory as the emerging model for an integration of data, models and tools applied to
the vehicle lifecycle is introduced with references to AAA research projects, publications and events.

3 décembre 2018

Descriptive distributed complexity

Fabian Reiter (IRIF)

This talk connects two classical areas of theoretical computer science:
descriptive complexity and distributed computing. The former is a branch of
computational complexity theory that characterizes complexity classes in terms
of equivalent logical formalisms. The latter studies algorithms that run in
networks of interconnected processors.

Although an active field of research since the late 1970s, distributed computing
is still lacking the analogue of a complexity theory. One reason for this may be
the large number of distinct models of distributed computation, which make it
rather difficult to develop a unified formal framework. In my talk, I will
outline how the descriptive approach, i.e., connections to logic, could be
helpful in this regard.