Réunions

Réunions en 2013

GdT - Mardi 9 juillet 2013, à 11h en Espace Communication

Stochastic Cellular Automata: Correlations, Decidability and Simulations

Joint work with Pablo Arrighi (LIG & LIP) and Guillaume Theyssier (LAMA).

The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in an unified and composable manner. We explore the consequences of allowing local probabilistic correlations and show that it allows strictly more behaviors (for instance, number conserving stochastic cellular automata are shown to require local stochastic correlation). In particular, we show that several problems looking deceptively simple become undecidable, even in dimension 1. We show that, despite that, 1D stochastic cellular automata have much simpler behavior and show how to solve some problems that becomes undecidable in dimension higher than 2. Armed with our formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the characterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.

Journée de l'équipe GAMoC, vendredi 7 juin 2013 à Orléans

Page de la journée GAMoC du vendredi 7 juin 2013

Réunion de l'ANR AGAPE, du lundi 28 janvier au vendredi 1er février 2013 à Orléans

Page de la réunion de l'ANR AGAPE - Orléans 2013

Réunions en 2012

GdT ‒ Jeudi 25 octobre 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Sur le nombre moyen de racines d'un polynôme réel aléatoire creux

Irénée Briquel (LIFO)

Le nombre moyen de racines réelles moyennes d’un polynôme réel à une variable dont les coefficients sont tirés au hasard est bien connu : asymptotiquement $2/\pi\ \log{d}$ lorsque les coefficients sont tirés suivant une gaussienne (Kac, 1943). Nous considérons ici des polynômes réels creux : les coefficients non nuls sont ceux d'indices $i_1, \ldots{}, i_k$ , et sont tirés aléatoirement suivant une distribution gaussienne uniforme. Nous montrons que le nombre de racines moyen est borné indépendamment du degré par $4/\pi\ k^{\frac{1}{2}} \log{k}$ .

La motivation de ces travaux sur le nombre de racines de polynômes réels creux vient d'une conjecture récente de Pascal Koiran. Sa tau-conjecture réelle stipule que toute somme de produits de polynômes creux a un nombre polynomial de racines réelles. Pascal Koiran a prouvé que cette conjecture implique la séparation des classes de Valiant VP° et VNP°.

Si cette conjecture semble très difficile, nous espérons pouvoir généraliser notre approche probabiliste sur les polynômes creux pour prouver cette conjecture en moyenne, pour des coefficients tirés aléatoirement. Un tel résultat nous renseignerait sur la difficulté de la conjecture générale.

Ces travaux sont menés conjointement avec Peter Bürgisser, de l'université de Paderborn.

Journée de l'équipe GAMoC ‒ Mardi 12 juin 2012 à Orléans

Page de la journée GAMoC du mardi 12 juin 2012

GdT ‒ Jeudi 19 avril 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Protocoles de population (Olivier Bournez)

Olivier Bournez
(LIX Polytechnique, Paris, France)

GdT ‒ Jeudi 5 avril 2012, à partir de 10h15 en salle SR1

Mots morphiques et schémas de récursion (Laurent Braud)

Laurent Braud
(LaBRI, Bordeaux, France)

GdT ‒ Mardi 3 avril 2012, à partir de 10h15 en salle SR1

Automates cellulaires réversibles, blocs de permutations et techniques quantiques (Vincent Nesme)

Vincent Nesme
(LRI, Paris Sud, France)

Comment implémenter un AC réversible par un circuit de portes réversibles ? On peut appliquer un bloc de permutation sur quelques cellules, puis répéter l'opération en divers endroits : on a une bonne décomposition si le nombre de couches est fini.

Des résultats de Kari et Durand-Lose montrent ce qu'il est possible de faire, avec ou sans espace auxiliaire, même s'il reste des questions ouvertes. Je vais tâcher de montrer ce qu'un point de vue quantique apporte : technique de décomposition plus intuitive et qui donne des blocs de taille minimale, calcul de cette taille par de la simple combinatoire.

GdT ‒ Mardi 27 mars 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Minimal dominating sets in graphs: enumeration, combinatorial bounds and graph classes (Dieter Kratsch)

Dieter Kratsch
(LITA, Université de Lorraine, Metz, France)

In 2008 Fomin, Grandoni, Pyatkin and Stepanov provided an exact exponential time algorithm to enumerate all minimal dominating sets of a graph. Its main consequence was the first non trivial upper bound on the number of minimal dominating sets; the maximum number of minimal dominating sets that a graph on n vertices can have is at most 1.7159^n. This upper bound might not be tight, since no examples of graphs with 1.5705^n or more minimal dominating sets are known.

This talk considers exact exponential algorithms to enumerate minimal dominating sets when the input graphs are restricted to certain graph classes, among them chordal graphs, cographs and chain graphs. The following types of results exploiting the structure of the particular graph classes are presented:
(i) enumeration algorithms based on branching algorithms and their analysis via upper bounding the number of leaves in search trees,
(ii) upper bounds on the maximum number of minimal dominating sets in n-vertex graphs obtained via branching algorithms or combinatorial proofs,
(iii) lower bounds on the maximum number of minimal dominating sets.

In some cases, we provide examples of graphs whose number of minimal dominating sets exactly matches the proved upper bound for that class, thereby showing that these bounds are tight.

Séminaire ‒ Jeudi 22 mars 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Complexity and algorithms for max-coloring problems (Giorgio Lucarelli)

Giorgio Lucarelli
(LIP6, Paris, France)

We deal with generalizations of the classical graph edge/vertex-coloring problems motivated by scheduling questions arising in computer and communication systems. The most general problems we attack are called bounded max-edge/vertex-coloring problems and take as input an edge/vertex weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest edge/vertex in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) max-coloring problems.

The max-coloring problems have been well motivated and studied in the literature. Max-edge-coloring problems arise in switch based communication systems, like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Max-vertex-coloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Moreover, max-coloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of the bounded max-coloring problems.

In this talk, we present complexity results as well as algorithms for the bounded max-edge/vertex-coloring problems.

Séminaire ‒ Mardi 20 mars 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Optimisation combinatoire dans les graphes : algorithmes exacts (Hadji Makhlouf)

Hadji Makhlouf
(Télécom SudParis, Paris, France)

Les travaux que je présenterai s'inscrivent dans le domaine de l'optimisation combinatoire. On utilise l'approche polyédrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. On introduit et étudie le problème d'optimisation des réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, on étudie de nouvelles variantes en intégrant de nouvelles contraintes techniques.

La première partie de cette présentation considère une contrainte portant sur la taille des cycles. On souhaite interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-difficile. Des inégalités valides seront alors proposées pour ce problème. On se focalise par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contraintes sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes.

Dans la deuxième partie, je présenterai de nouveaux problèmes d'optimisation combinatoires appliqués sur le Cloud Computing. Plus précisément, je présenterai un problème d'allocation de ressources limitées chez les fournisseurs de services, et partagées par un ensemble d'utilisateurs. On applique la théorie des jeux pour décrire l'équilibre de Nash/Stackelberg satisfaisant tous les acteurs du jeu. Je présenterai aussi le problème d'allocation de ressources dans une fédération de cloud providers et je proposerai un algorithme exacte s'appuyant sur un ensemble d'inégalités. Je termine par présenter un algorithme de flot maximum de coût minimum pour allouer d'une manière dynamique les ressources d'un fournisseur de services à un ensemble d'utilisateurs. Le problème est alors modélisé sous forme d'un graphe orienté sur lequel on calcule le flot maximum.

GdT ‒ Mardi 14 février 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Quelques aspects du modèle de piles de sable de Kadanoff (Éric Rémila)

Éric Rémila
(LIP, ENS Lyon, France)

GdT ‒ Jeudi 5 janvier 2012, à partir de 10h15 en salle A02 (M2 Recherche)

Colouring AT-free graphs (Haiko Müller)

Haiko Müller
(Université de Leeds, UK)

Three vertices of a graph form an asteroidal triple (short AT) if between any two of them there is a path avoiding all neighbours of the third. This concept was introduced by Lekkerkerker and Boland in 1962 to characterise interval graphs as those chordal graphs having no AT. Asteroidal triple-free graphs form a graph classes with a lot of interesting structural and algorithmic properties; most of them discovered in the late nineties initiated by the important work of Corneil, Olariu and Stewart.

A vertex colouring assigns to each vertex of a graph a colour such that adjacent vertices have different colours. The algorithmic complexity of the COLOURING problem, asking for the smallest number of colours needed to vertex colour a given graph, is known for a huge number of graph classes. In fact, it is solvable in polynomial time for perfect graphs, and thus for all their subclasses.

Broersma et al. asked to find out the algorithmic complexity of COLOURING on AT-free graphs. Even the algorithmic complexity of the k-COLOURING problem, which asks whether a graph can be coloured with a fixed number k of colours, remained unknown for AT-free graphs until recently; for k=3 Stacho presented a polynomial time algorithm. We show that k-COLOURING is polynomial-time solvable on AT-free graphs.

Précédentes réunions