How efficiently can we find an unknown graph using shortest path queries between its vertices? This is a natural theoretical question from the standpoint of recovery of hidden information. This question is related to discovering the topology of Internet networks, which is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.

In this talk, I will introduce the problems of graph reconstruction and verification via oracles. I will investigate randomized algorithms based on a Voronoi cell decomposition. I will also analyze greedy algorithms, and prove that they are near-optimal.

The talk is based on joint work with Claire Mathieu and Sampath Kannan.

Bertrand et al. (2017) introduced a model of parameterised
systems, where each agent is represented by a finite state system, and
studied the following control problem: for any number of agents, does
there exist a controller able to bring all agents to a target state? They
showed that the problem is decidable and EXPTIME-complete in the
adversarial setting, and posed as an open problem the stochastic setting,
where the agent is represented by a Markov decision process. In this
paper, we show that the stochastic control problem is decidable. Our
solution makes significant uses of well quasi orders, of the max-flow min-
cut theorem, and of the theory of regular cost functions.

Afin d’étudier les propriétés combinatoires des suites infinies, une approche fructueuse consiste à étudier un sous-shift, i.e. un ensemble fermé de suites, invariant par l’action du shift (décalage), associé à ces suites. La théorie des systèmes dynamiques fournit alors des outils pertinents.
Une question classique consiste alors à étudier les symétries de ces systèmes dynamiques, i.e. les auto-conjugaison du système. Dans ce contexte, Morse et Hedlund ont montré que ces auto-conjugaisons correspondent aux automates cellulaires préservant le sous-shift.
Le groupe engendré par ces transformations est toujours dénombrable en général difficile à décrire.
Dans cet exposé, nous présenterons un survol de récentes avancées dans l’étude de ce groupe et notamment ses relations avec la complexité du système symbolique.

Énumérer des objets est une tâche courante en informatique,  que ça soit pour les compter, trouver une solution optimale ou constituer une librairie d’objets intéressants.  Un problème typique est de devoir gérer la répétition d’objets identiques (donc inutiles) lors du processus d’énumération. La seule difficulté dans l’énumération des modèles d’une formule DNF est de cette nature. Cela a pour conséquence que les algorithmes habituels utilisent un temps linéaire en la taille de la formule par modèle. Les modèles pouvant être exponentiellement plus petit que la formule, on voudrait donc obtenir un temps linéaire (ou polynomial) en chaque modèle. Nous conjecturons que de tels algorithmes n’existent pas. Néanmoins nous allons montrer comment on peut relâcher le problème ou restreindre les entrées et ainsi proposer plusieurs techniques pour générer ces modèles en temps sous linéaire (par solution générée) voire en temps constant.

In this talk, we will show how one can augment classes of Boolean
circuits used in knowledge compilation so that one can efficiently check that
they are equivalent to a given CNF formula. We will show that it can be applied
to define Cook-Reckhow proof systems for #SAT and maxSAT and how one can use
this idea to output certificates from existing tools solving #SAT.

Un grand nombre d’automates cellulaires ont été donnés sous forme de table de transition construite à la main. La méthodologie des “champs cellulaires” donne les principes de conception modulaire et de génération de la table de transition en dernière étape, comme c’est le cas pour le code source d’un langage de programmation de haut niveau et leur fichier exécutable binaire. Nous vérifions si les tables ainsi générées peuvent être optimisées pour être aussi petites que leurs contreparties construites à la main. Ceci est fait dans le cas particulier d’un automate cellulaire qui résout le problème de synchronisation des fusiliers (Firing Squad Synchronization problem en anglais) en utilisant des champs cellulaires. Nous étudions la structure interne de cette solution et ainsi que des notions de réduction dans la même veine que la minimisation des automates finis déterministe. La comparaison est faite avec la solution “à la main” de Noguchi.

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.