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

4 novembre 2019

TBA

Tien Thao N’guyen (LACL)

TBA

14 octobre 2019

Relaxations Sherali-Adams pour les VCSPs

Johan Thapper (LIGM - UPEM)

The valued constraint satisfaction problem (VCSP) is a framework for describing and studying many classes of discrete optimisation problems. It is an optimisation version of the constraint satisfaction problem (CSP), where the goal is to decide whether one can assign labels to variables under some given set of constraints. The VCSP captures both Max CSP-type problems, where one wants to optimise the number of satisfied constraints, and integer programming-type problems, where one adds an objective function to an ordinary CSP to indicate the desirability of each solution.

I will talk about algorithms and hardness results for VCSPs where we restrict the types of cost functions that are allowed to appear in the description of an instance. The algorithms that I consider are based on linear programming (LP), in particular LP relaxations in the Sherali-Adams hierarchy. It turns out that for large classes of VCSPs, there is a complete dichotomy between problems that can be solved by this type of algorithm and problems that can encode NP-hard problems.

7 octobre 2019

Soutenance HDR – Subshifts: aperiodicity, complexity and groups

Pascal Vanier (LACL - UPEC)

Les sous-shifts sont des coloriages de $\mathbb{Z}^d$ verifiant des contraintes locales. Très tôt l’étude de sous-shifts en dimension supérieure à 2 a vu deux notions apparaître naturellement : l’apériodicité et l’indécidabilité. Nous explorons ces deux notions dans ce manuscrit, la seconde par le prisme de différentes notions de complexité, puis nous introduisons un nouveau regard sur les sous-shifts par le biais d’analogies avec la théorie des groupes.

Les sous-shifts sans point périodique, dits apériodiques, ont fait leur apparition avec la construction de Berger prouvant l’indécidabilité de la pavabilité du plan avec le formalisme des tuiles de Wang. Les sous-shifts apériodiques
ont ensuite été l’ingrédient principal de la plupart des constructions. Dans ce document nous nous intéressons
à la notion duale qui consiste à contenir un point apériodique. Nous montrons que les sous-shifts contenant un
point apériodique en contiennent toujours avec une apériodicité régulière : dans des boules concentriques
dont le rayon ne dépend que de la période.

La complexité dans les sous-shifts peut prendre plusieurs formes. Nous illustrons ici les différents liens qui unissent certaines de ces notions de complexité : complexité de Kolmogorov, complexité des configurations via le spectre des degrés Turing, ainsi que complexité au sens du nombre de motifs.

Nous introduisons en fin de manuscrit des analogies avec la théorie des groupes qui nous permettent d’énoncer
des analogues aux théorèmes de Higman dans le cadre des sous-shifts.