On monday, at 2pm - UPEC CMC - Room P2-131

February 3, 2020

Network Inference: Graph reconstruction and verification

Hang Zhou (LIX - Polytechnique)

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.

January 27, 2020

Controlling a random population

Pierre Ohlmann (IRIF)

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.

January 20, 2020

Sur les automates cellulaires préservant un sous-shift.

Samuel Petite (LAMFA - Université de Picardie)

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.

January 13, 2020

Énumération des modèles d’une formule DNF en délai sous linéaire

Yann Strozecki (Laboratoire DAVID )

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

November 25, 2019

Subgame Perfect Equilibria in (quantitative) Reachability Games

Marie Van Den Bogaard (ULB )

In this talk, we consider multiplayer games on graphs. In such games, each player has his own objective, that does not necessarily clash with the objectives of the other players. In this “non zero-sum” context, equilibria are a better suited solution concept than the classical winning strategy notion. We will focus on a refinement of the well-known Nash Equilibrium concept:  Subgame Perfect Equilibrium (SPE for short), where players have to play rationnally in every scenario, even the one deviating from the planned outcome. We will explain why this refinement is a relevant solution concept in multiplayer games and show how to handle them in reachability games, both in the qualitative and quantitative setting.

November 18, 2019

Proof systems for #SAT

Florent Capelli (Université de Lille)

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.

November 4, 2019

Première étape dans l’optimisation des champs cellulaires : une étude dans le cadre du problème de synchronisation des fusiliers

Tien Thao N’guyen (LACL)

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.

October 14, 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.