Archives du groupe de travail

Duality for dummies
Laurent Lyaudet

Dans cet exposé au titre provocateur, j'espère convaincre mon auditoire que tous les résultats de dualité pour les décompositions de graphes sont la conséquence d'un résultat trivial de dualité pour les décompositions d'ensembles finis arbitraires.

Lower Bounds for Satisfiability and Related Problems
Dieter van Melkebeek (University of Wisconsin)

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time logarithmic-space algorithm was not ruled out.

Recent years have seen considerable progress in time-space lower bounds for satisfiability and closely related problems on deterministic, randomized, and quantum machines. This talk will survey the state-of-the-art and give a flavor of the arguments involved.

Connexité des espaces de pavage avec un flip restreint
Bertrand Marc

La théorie des pavages sur les dominos a produit de nombreux résultats, basés sur des flips locaux. Ces flips consistent à tourner de 90° un carré 2x2 s'il contient exactement 2 tuiles. Dans ce cas classique, on sait que l'on peut passer d'un pavage à tout autre grâce à ces flips, et que cela induit une structure de treillis distributif sur l'espace des pavages.

Nous avons travaillé avec un flip plus restrictif, sur un rectangle 3x2. Nous montrons que dans ce cas il y a plusieurs composantes connexes que l'on peut caractériser. Chacune des ces composantes connexes a une structure de treillis distributif. Enfin, l'étude des marches aléatoires dans ces composantes connexes est plus difficile que dans le cas classique, et le temps de mélange n'est pas toujours rapide.

Automates Cellulaires 2D : Exemples de comportement asynchrones
Lucas Gérin

Il y a une tradition lyonnaise d'étudier la robustesse de certains automates cellulaires, en particulier la perturbation induite par l'asynchronisme : au lieu de mettre à jour toutes les cellules à chaque étape, on n'en met à jour qu'une partie aléatoire. Je présenterai un travail en cours avec Nazim Fatès dans lequel nous avons étudié le comportement asynchrone de certains AC à deux états, sur une grille finie. Certains résultats sont semblables à ceux obtenus en dimension 1, d'autres très différents.

transparents

Densité et propriétés dans les automates cellulaires
Laurent Boyer

On introduit la notion de densité des propriétés des automates cellulaires. Puis on s'intéresse plus particulièrement à certaines propriétés comme l'universalité pour des classes restreintes d'automates. On monte qu'il existe des classes naturelles d'automates presque tous universels, à l'image des AC captifs mais dans un cadre un peu plus général.

Problèmes de satisfaction de contraintes : essai de transposition d'un théorème de dichotomie
Irénée Briquel

Soit S un ensemble de contraintes booléennes. On appelle SAT(S) le problème de satisfaction de contraintes appartenant à S. Par exemple, 3-SAT est SAT(S) où S est l'ensemble des 3-clauses. Un théorème connu de Schaeffer dit que Suivant S, SAT(S) est soit dans P, soit NP-complet. On caractérise en outre très facilement les ensembles S tels que SAT(S) est dans P, ou SAT(S) est dans NP. Par exemple, 2-SAT est dans P, 3-SAT est NP-complet.

Ce résultat a été transposé aux problèmes de comptage par Creignou et Hermann : #SAT(S) est le problème de comptage du nombre de solutions de contraintes appartenant à S. À nouveau, #SAT(S) est soit dans FP (calculable en temps polynomial), soit #P-complet. Cependant, la frontière entre problèmes faciles et difficiles a bougé : cette fois-ci #-2-SAT est #P-complet ! En fait #SAT(S) est #P-complet ssi S n'est pas réduit à des contraintes affines. Nous proposons un équivalent algébrique de ces problèmes de satisfaction de contraintes, et tentons de le situer dans le modèle de Valiant :

• Nous définissons naturellement un polynôme P(S) associé à chaque ensemble S.
• Nous montrons que pour les ensembles S non réduits à des contraintes affines, P(S) est VNP-complet (sous une définition large de cette complétude).
• Pour les contraintes affines, nous ne savons pas conclure (et sommes preneurs si vous avez des idées !).

Abstract geometrical computation et le modèle de Blum, Shub and Smale
Jérôme Durand-Lose

Après avoir défini les deux modèles de calcul analogique, nous montrerons qu'AGC sans accumulation est équivalant à BSS linéaire (i.e. on ne peut multiplier qu'avec des constantes) avec un nombre infini de registres. Si l'on autorise des accumulations simples dans AGC, alors on peut aussi faire des multiplications, mais également extraire des racines ce qui est strictement plus que BSS complet.

Automate minorité sur les arbres
Jean-Baptiste Rouquier

La règle de minorité est un automate cellulaire à deux états qui consiste simplement à passer dans l'état minoritaire parmi ses voisins (et ne pas changer d'état en cas d'égalité). Il modélise par exemple des agents cherchant à minimiser les nuisances sur les voisins, ou bien est une stratégie simpliste dans le classique minority game. Nous étudions cette règle dans le cas asynchrone. Le cas 2D a été étudié par Damien Regnault, Nicolas Schabanel et Éric Thierry. Dans le but d'appréhender l'influence de la topologie, nous nous sommes penchés sur une topologie simple, sans boucles : les arbres.

Après quelques outils génériques à plusieurs topologies, nous verrons l'influence du degré sur le temps de convergence vers l'ensemble limite, comment tester ce dernier et, si le temps le permet, sa structure.

Travail en commun avec Damien Regnault et Éric Thierry.

Combinatoire des mots et conjecture de Fraenkel
Laurent Vuillon

Ce séminaire donnera les liens entre un problème de recouvrement des entiers et la combinatoire des mots afin d'étudier la conjecture de Fraenkel. Cette conjecture a été formulée dans le cadre de la théorie des nombres il y a maintenant plus de 30 ans. Elle prétend que pour k > 2 entier fixé, il y a une unique façon de recouvrir les entiers par k suites de Beatty avec des fréquences deux à deux distinctes.

Ce problème peut être exprimé en termes de combinatoire des mots de la façon suivante: pour un alphabet à k lettres, il existe une unique suite équilibrée avec des fréquences de lettres deux à deux distinctes qui est exactement la suite de Fraenkel notée (Fr_k^ω où Fr_k = Fr_k-1 k Fr_k-1, avec Fr₃ = 1213121. Cette conjecture est prouvée pour k ∈ {3, 4, 5, 6} d'après les travaux de Altman, Gaujal, Hordijk et Tijdeman ainsi que dans d'autres cas particuliers. Dans ce séminaire, nous présenterons donc une synthèse sur ce sujet et la résolution de la conjecture dans un cas particulier.

transparents

Signaux et pavages auto-assemblant
Florent Becker

Les pavages auto-assemblants constituent un modèle de construction de figures planes qui permet d'utiliser la chimie et en particulier les propriétés de l'ADN pour calculer. Les mécanismes chimiques qui permettent de l'implémenter commencent à être compris, mais pour programmer dans ce cadre, un formalisme de calcul géométrique est nécessaire. Je présenterai une adaptation à l'auto-assemblage des systèmes de signaux que l'on trouve dans l'étude des automates cellulaires. Nous verrons comment dessiner diverses formes avec ces outils, et comment transformer ces jolis dessins en tuiles qui les auto-assemblent.

Avec trois exemples édifiants, les carrés, les polygones convexes et le pavage de Robinson.

transparents

Ordonnancement non-clairvoyant avec dépendances
Julien Robert

Dans cet exposé, je parlerai d'ordonnancement en ligne non-clairvoyant avec dépendances. Le modèle étudié est le suivant : différents jobs arrivent au cours du temps et sont composés de tâches dépendant les unes des autres (graphe acyclique orienté) ; chaque tâche ayant un degré de parallélisme variant au cours de son exécution. On se place dans le modèle en-ligne : les jobs ne sont connus qu'au moment de leur arrivée ; et non-clairvoyant : les caractéristiques des jobs et des tâches sont inconnues de l'ordonnanceur. Un job est considéré comme terminé lorsque toutes ses tâches sont exécutées ; son temps d'attente est alors le temps écoulé entre sa date d'arrivée et le moment auquel il s'est terminé. L'objectif est de minimiser le temps moyen d'attente des jobs. Dans ce modèle, la stratégie EQUIoEQUI répartit les jobs équitablement entre les processeurs, puis, pour chaque job, réparti ses tâches équitablement. Nous verrons que le temps moyen d'attente des jobs dans EQUIoEQUI est au plus à un facteur O(k/ε) du temps d'attente moyen des jobs d'une stratégie optimale, clairvoyante et hors-ligne, mais sur 2+ε fois moins de processeurs, où k est le nombre maximal d'anti-chaînes d'un job.

Décomposition modulaire, relations homogènes et généralisations
Vincent Limouzy

La décomposition modulaire est une décomposition de graphes qui a été très étudié aux cours des dernières décennies. Elle a été introduite pour la première fois par T. Gallai en 1967... et redécouverte à plusieurs reprises notamment en sciences sociales, et en bio-informatique.

Dans cet exposé nous rappellerons la définition et les propriétés intéressantes de la décomposition modulaire. Nous montrerons ensuite comment le concept de casseur permet d'étendre cette dernière à d'autres structures que les graphes. Pour ce faire nous introduirons les relations homogènes, structure qui généralise les graphes.

Nous présenterons également une nouvelle décomposition, celle-ci appellée umodulaire, et présenterons les premières propriétés de cette dernière. Qui fournit une tout nouvelle décomposition des tournois.

transparents

Décomposition de graphes en plusieurs facteurs
Martín Matamala

In this talk, I will present an overview of some results about decompositions of graphs into factors. For a given graph, a factor is a subgraph with prescribed degrees. For instance, a 1-factor is a perfect matching. A decomposition of a graph is a partition of its edge set where each part in the partition induces a given factor. While the decomposition of a graph into two factors is polynomially solvable, when three factors are considered the problem becomes NP-complete, even in very restricted classes of graphs. I will also discuss some open problems and how we think they could be tackled.

transparents

Temps linéaire et énumération de requêtes à délai constant
Étienne Grandjean (GREYC, Université de Caen)

La notion de temps linéaire dans le modèle RAM constitue un lien précis entre l'algorithmique et la théorie de la complexité. La complexité en temps linéaire est une notion robuste, naturelle et pratique. Dans cet exposé, je présenterai d'abord quelques exemples en algorithmique et sur les requêtes en bases de données qui témoignent de l'importance du temps linéaire en pratique. Je décrirai succinctement un ensemble de problèmes de "model-checking" (est-ce qu'une structure S satisfait un certain énoncé logique F?) dont la complexité en temps est linéaire (en la taille de la structure S): il s'agit des formules conjonctives acycliques (formules ACQ de Yannakakis), essentielles dans les bases de données.

On peut aller plus loin encore: le calcul de l'ensemble des "tuples", noté F(S), qui satisfont une formule fixée F (conjonctive acyclique) sans quantificateur dans une structure (= base de données) S - est calculable en temps linéaire en la taille de l'entrée (la structure S) + la taille de la sortie (l'ensemble de tuples F(S)). Plus finement encore, il existe, pour chaque requête F, un algorithme qui, après un précalcul linéaire (en la taille de S), énumère les tuples du résultat à délai constant. La classe d'algorithmes d'énumération ainsi mise en évidence, appelée CONSTANT-DELAY(lin), s'avère encore une notion de complexité robuste et, en un certain sens, minimale. De plus, elle s'applique à plusieurs autres classes de requêtes, et en particulier à toutes celles définies sur les logiques et structures suivantes:

• les formules conjonctives acycliques avec inégalités (et sans quantificateur), là encore sur toutes les structures (= bases de données quelconques),
• la logique du premier ordre FO (First Order) sur les graphes de degré borné,
• la logique monadique du second ordre MSO (Monadic Second Order) sur les arbres.

Hierarchies for Semantic Models of Computation
Dieter van Melkebeek (université de Madison, Wisconsin, État-Unis)

A basic question in computational complexity asks whether somewhat more time allows us to solve strictly more decision problems on a given model of computation. Despite its fundamental nature, the question remains unanswered for many models of interest. Essentially, time hierarchies are known for every syntactic model of computation but open for everything else.

There has been significant progress in recent years, namely in establishing time hierarchies for non-syntactic models with small advice. In this talk, we survey these results and present a generic theorem that captures and strengthens all of them. We show that for any reasonable model of computation and for any constants 1 ≤ c ≤ d, there exists a language computable in time n^d with one bit of advice but not in time n^c with one bit of advice.

Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur-Merlin games of any signature, etc. Our argument also yields considerably simpler proofs of earlier hierarchy theorems with one bit of advice for randomized or quantum machines with two-sided error.

We will also discuss similar results for space rather than time.

This talk is based on joint work with Jeff Kinne and Konstantin Pervyshev.

How Far Are We from Proving Circuit Size Lower Bounds?
Eric Allender

Many people are pessimistic about seeing a resolution to the P vs NP question any time soon. This pessimism extends also to questions about other important complexity classes, including two classes that will be the focus of this talk: TC⁰ and NC¹. TC⁰ captures the complexity of several important computational problems, such as multiplication, division, and sorting; it consists of all problems computable by constant-depth, polynomial-size families of circuits of MAJORITY gates. TC⁰_d is the subclass of TC⁰ solvable with circuits of depth d. Although TC⁰ seems to be a small subclass of P, it is still open if NP = TC⁰₃.

NC¹ is the class of problems expressible by Boolean formulae of polynomial size. NC¹ contains TC⁰, and captures the complexity of evaluating a Boolean formula.

Any proof that NP is not equal to TC⁰ will have to overcome the obstacles identified by Razborov and Rudich in their paper on "Natural Proofs". That is, a "natural" proof that NP is not equal to TC⁰ yields a proof that no pseudorandom function generator is computable in TC⁰. This is problematical, since some popular cryptographic conjectures imply that such generators do exist. This leads to pessimism about the even more difficult task of separating NC¹ from TC⁰.

Some limited lower bounds are within the grasp of current techniques, however. For example, several problems in P are known to require formulae of quadratic size – but this seems to be of little use in trying to prove superpolynomial formula size. Along similar lines, it is known that, for every d, there is a constant c>1 such that the formula evaluation problem (one of the standard complete problems for NC¹) requires TC⁰_d circuits of size at least n^c.

It might not seem too outrageous to hope to obtain a slightly stronger lower bound, showing that there is a c>1 such that this same set requires uniform TC⁰ circuits of size n^c (regardless of the depth d). We show that this would be sufficient to prove that TC⁰ is properly contained in NC¹.

This is joint work with Michal Koucký.

Approximate Satisfiability and Equivalence
Michel de Rougemont (université Paris 2)

We show how to approximate decision problems such as satisfiability of a formula by a structure, or equivalence between two formulas, such that we gain an exponential factor or more in complexity. Typical case is to decide if two non-deterministic automata are equivalent: we decide the approximate version in polynomial time whereas the exact version is PSPACE complete. For pushdown automata, we decide the approximate version in exponential time whereas the exact version is undecidable.

Quantum Matchcircuits
Yao Penghui

Valiant defined the notions of matchgates and matchcircuits, and showed that any quantum circuits that are also matchcircuits can be efficiently simulated classically. In this talk, we study the quantum matchgates and quantum matchcircuits. We show that the 2-level quantum matchgates are universal for the quantum matchcircuits, that quantum circuits can be realized by the compositions of 2-level quantum matchgates and the control-not gate (CNOT), that for any 2-level quantum matchgate with character matrix A, there exists a 2-level quantum matchgate with character matrix T such that T ^-1AT=B, where B is diagonal, and that the distance between the control-not gate and the quantum matchgates under the Hilbert-Schmidt norm has a lower bound 2√(2-√2).

Finding Optimal Flows Efficiently
Simon Perdrix (université d'Oxford)

Joint work with Mehdi Mhalla (LIG, Grenoble).

Among the models of quantum computation, the One-way Quantum Computer is one of the most promising proposals of physical realization, and opens new perspectives for parallelization by taking advantage of quantum entanglement. Since a one-way quantum computation is based on quantum measurement, which is a fundamentally nondeterministic evolution, a sufficient condition of global determinism has been introduced as the existence of a causal flow in a graph that underlies the computation.

A O(n³) algorithm has been introduced for finding such a causal flow when the numbers of output and input vertices in the graph are equal, otherwise no polynomial time algorithm was known for deciding whether a graph has a causal flow or not. Our main contribution is to introduce a O(n²) algorithm for finding a causal flow, if any, whatever the numbers of input and output vertices are. This answers the open question stated by Danos and Kashefi and by de Beaudrap. Moreover, we prove that our algorithm produces an optimal flow (flow of minimal depth).

Whereas the existence of a causal flow is a sufficient condition for determinism, it is not a necessary condition. A weaker version of the causal flow, called gflow (generalized flow) has been introduced and has been proved to be a necessary and sufficient condition for a family of deterministic computations. Moreover, the depth of the quantum computation is upper bounded by the depth of the gflow. However, the existence of a polynomial time algorithm that finds a gflow has been stated as an open question. In this paper we answer this positively with a polynomial time algorithm that outputs an optimal gflow of a given graph and thus finds an optimal correction strategy to the nondeterministic evolution due to measurements.

transparents

Self-stabilizing synchronization in 3 dimensions
Peter Gacs (Boston University)

En collaboration avec Matthew Cook (ETH) et Erik Winfree (California Institute of Technology)

The simplest known fault-tolerant model of computation is the three-dimensional cellular automaton introduced by Gacs and Reif. This automaton works only in discrete time; the only known asynchronous reliable cellular automata are vastly more complex. A simple scheme based on a modulo 3 clock is known to introduce asynchrony into any kind of network. However, errors can bring the local clocks into an inconsistent state (cycles). We found a relatively simple way to resolve localized topological inconsistencies of arbitrary size, at least in the absence of further errors.

transparents

Sur les algorithmes accidentels/holographiques de Valiant
Yann Strozecki

Valiant a introduit en 2001 une nouvelle manière de construire des algorithmes calculant des fonctions de comptage. Il s'agissait au départ de simuler de manière classique une partie de l'informatique quantique. Nous allons nous y intéresser pour montrer qu'un certain nombre de problèmes qui ont l'air d'être #P-complets sont en fait facile à calculer. L'exposé ne requiert aucune connaissance particulière mais demande un peu de goût pour l'algèbre de base et les graphes.

transparents

Relations d'équivalence sur l'espace des mesures calculables
Laurent Bienvenu (LIF, Marseille)

La notion d'équivalence entre deux mesures de probabilités est centrale en théorie classique de la mesure, et plus particulièrement en théorie des probabilités. Deux mesures sont dites équivalentes si elles admettent les mêmes ensembles de mesure nulle. En se plaçant dans l'espace de Cantor (i.e. des suites binaires infinies), on peut définir de façon naturelle une notion de mesure calculable et, à partir de cette notion, diverses versions effectives de la relation classique d'équivalence. Nous étudierons les liens entre ces différentes relations d'équivalence, notre étude faisant intervenir de façon centrale la théorie algorithmique de l'aléatoire ainsi que la théorie des degrés de Turing.

transparents

The word problem for a class of groups with infinite presentation
Klaus Meer

The word problem for discrete groups is well-known to be undecidable by a Turing Machine; more precisely, it is reducible both to and from and thus equivalent to the discrete Halting Problem. The present work introduces and studies a real extension of the word problem for a certain class of groups which are presented as quotient groups of a free group and a normal subgroup. The main result establishes the word problem for such groups to be computationally equivalent to the Halting Problem for BSS machines over the reals.

It thus provides the first non-trivial example of a concrete problem that is computationally universal for the BSS model.

Travail en collaboration avec Martin Ziegler, Paderborn

Quelques avancées dans l'analyse des automates cellulaires stochastiques 2D
Une étude de Minorité 2D asynchrone
Nicolas Schabanel

Après un petit tour des différents thèmes qu'on a développés cette année (ordonnancement non-clairvoyant, marketing viral, systèmes dynamiques discrets probabilistes), je vous proposerai un exposé sur nos derniers résultats sur l'analyse probabiliste d'automates cellulaires asynchrone 2D. Au programme : de jolies animations, de beaux dessins, de la physique statistique et de mignons petits théorèmes accessibles à tous.

Les automates cellulaires sont utilisés en physique, sciences sociales, biologie, pour modéliser des systèmes qui sont bien souvent intrinsèquement asynchrones. Durant ces 20 dernières années, des études ont démontré que le comportement de ces automates, même les plus simples, changeait complètement lorsque les mises à jour se font de façon asynchrone. Pourtant, très peu d'études mathématiques parviennent à l'expliquer. La plupart porte sur le cas unidimensionnel, et encore sur quelques automates ou classes d'automates particulières. De même que pour de nombreux systèmes dynamiques en physique, la généralisation des méthodes développées pour les cas unidimensionnel à des dimensions supérieures demeure un véritable défi.

Dans cet exposé, nous présenterons quelques résultats sur l'analyse d'un automate 2D : Minorité, où chacun passe dans l'état minoritaire de son voisinage (par pur esprit de contradiction, ou bien afin de minimiser les nuisances dues à son voisinage (interférences sur la fréquence choisie dans le cas des réseaux de senseurs par exemple)). Nos expérimentations ont démontré que Minorité répond de façon plutôt complexe à l'asynchronisme malgré son apparente simplicité. Dans l'étude du régime totalement asynchrone (cas typique d'étude en physique et mathématiques), nous avons pu décrire complètement le comportement asymptotique en se restreignant à des configurations initiales naturelles. Nous avons de bonnes raisons d'espérer que les techniques que nous avons développées, utilisant une fonction d'énergie définie à partir des règles de transition de l'automate, peuvent s'étendre à la classe importante des automates à seuil (utilisés en particulier dans la modélisation des réseaux de neurones).

Travail en commun par Damien REGNAULT (CMM, U de Chile - ENS LYON), Nicolas SCHABANEL (CMM, U de Chile), et Éric THIERRY (ENS LYON)

transparents

Acyclicity of Preferences, Nash Equilibria, and Subgame Perfect Equilibria: Two Proofs of the Equivalence
Stéphane Leroux

Topic: Game theory.

Prerequisites: basic discrete mathematics (binary relation, tree, induction).

Sequential game and Nash equilibrium are basic key concepts in game theory. In 1953, Kuhn showed that every sequential game has a Nash equilibrium. Traditionally, sequential games involve real-valued payoff functions. I replace them with abstract atomic objects and generalise Kuhn's result to such an extent that I get an equivalence property. I provide two proofs very different from a proof theoretic viewpoint.

transparents

Automates sur les chaînes
Olivier Carton

Dans cet exposé, on parlera d'automates acceptant des mots indicés par des ordres totaux (chaînes). Ces automates sont des objets simples, qui généralisent de façon naturelle les automates sur les mots finis, les mots infinis, les mots bi-infinis et les mots indicés par des ordinaux.

Les langages de mots acceptés par ces automates sont aussi les langages décrits par des opérations rationnelles bien choisies (théorème à la Kleene). Celles-ci généralisent les opérations rationnelles connues pour les mots finis.

On parlera aussi du problème de la complémentation de ces ensembles de mots ainsi que des liens avec la logique.

Le show des thésards
Laurent Lyaudet, Victor Poupet, Florent Becker et Sylvain Périfel

Résumé (par ordre alphabétique des présentateurs)

Florent Becker : les fractales, c'est fascinant et facile à dessiner. Les automates cellulaires, tout le monde aime ça. Et des automates cellulaires qui remplissent le plan de fractales, n'est-ce pas formidable ?

Laurent Lyaudet : est-ce que vous avez déjà essayé d'enfermer un serpent agressif dans un hypercube ?

Sylvain Perifel : avec des circuits, on peut aussi calculer des ensembles d'entiers... On essaiera de mesurer ces ensembles.

Victor Poupet : j'essaierai de présenter une idée qui me paraissait rigolote (mais qui ne mène nulle part pour le moment) qui consiste à définir, pour une proposition P et un mot w de Σⁿ, la quantité d'information sur w que contient P.

Quantum lower bounds through spectral analysis
Peter Hoeyer (Calgary)

Quantum computers are powerful: they can for instance efficiently factorize large integers, solve algebraic problems, and find hidden structures. But what can quantum computers NOT do efficiently? One of the strongest techniques for proving limits on quantum computers is by applying so-called adversary arguments. We give a gentle introduction to the adversary method, present a new strengthening of the method, and apply it on several examples, yielding improved bounds on the limits of quantum computers. No prior knowledge of quantum mechanics or quantum computing is required.

Aspects structurels des pavages
Alexis Ballier (Marseille)

On s'intéresse à l'étude des propriétés structurelles des pavages du plan discret. Un moyen naturel et souvent utilisé est de comparer l'ensemble des motifs finis qu'ils contiennent ; un autre, basé sur la dérivée topologique, permet d'obtenir d'autres résultats. Nous définirons ces deux approches indépendantes, présenterons des résultats apportés par l'une ou l'autre pour enfin combiner ces deux points de vue différents (combinatoire pour le premier, topologique pour le second) et obtenir de nouveaux résultats sur la structure des pavages produits par un jeu de tuiles.

transparents

Simulation classique de corrélations quantiques
Sophie Laplante (LRI, Orsay)

Largeur linéaire (pathwidth) et complétions d'intervalles minimales
Ioan Todinca (université d'Orléans)

Les graphes étant des objets complexes, on tente souvent de les «simplifier» si possible sans leur apporter beaucoup de modifications. Une technique courante consiste à ajouter des arêtes au graphe en entrée afin d'obtenir un graphe plus simple. Une complétion d'intervalles d'un graphe quelconque G est un graphe d'intervalles H, obtenu à partir de G en lui ajoutant des arêtes. On cherche classiquement à minimiser certains paramètres comme le nombre d'arêtes ajoutées ou la taille de la clique de cardinal maximum de H.

Ces problèmes étant NP-difficiles, nous nous intéressons aux complétions d'intervalles minimales, où l'on demande simplement à ce que l'ensemble d'arêtes ajoutées soit minimal par inclusion. Je montrerai comment extraire une telle complétion à partir d'une complétion non minimale et je présenterai un algorithme de calcul de la largeur linéaire pour les graphes d'intervalles circulaires.

transparents

Une borne inférieure quadratique pour le problème du permanent et du déterminant
Nicolas Ressayre (université Montpellier)

Nous appelons complexité déterminantale d'un polynôme f en les variables x₁,...,x_s la taille minimale d'une matrice M de formes affines en les x_i dont le déterminant vaut f. D'après un résultat de Valiant, cette complexité est toujours finie et est une bonne mesure de la complexité plus naturelle en termes de longueur de formules arithmétiques définissant f. Nous commencerons par calculer la complexité déterminantale des polynômes homogènes de degré 2.

Le polynôme permanent Per_d de degré d en les d² entrées d'une matrice carrée de taille d joue un rôle central dans la théorie de Valiant. Une conjecture de Valiant affirme même que la complexité déterminantale de Per_d n'est majorée par aucun polynôme en d. Nous montrerons dans cet exposé comment des arguments géométriques très simples permettent de montrer que la complexité détermiantale de Per_d est supérieure à d²/2.

Firing Squad Synchronization Protocols for Communication-restricted Cellular Automata
Hiroshi Umeo

transparents

GPAC, Analyse récursive, fonctions R-récursives sont des modèles de calcul sur les réels équivalents
Emmanuel Hainry (Nancy)

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d'autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent les mêmes fonctions. Nous allons présenter trois modèles de calcul sur les réels : le GPAC, l'analyse récursive et les fonctions R-récursives, puis montrer qu'en utilisant une bonne définition de ce qui est calculable, ces modèles sont équivalents. Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels.

transparents

Recent developments in Firing Squad Syncronization Problem algorithms for two-dimensional cellular arrays.
Hiroshi Umeo

Symétrie de l'information et bornes inférieures non-uniformes
Sylvain Périfel

Le théorème de hiérarchie en temps montre qu'il existe des problèmes décidables en temps exponentiel n'ayant pas d'algorithme polynomial. En revanche, la question de savoir s'ils peuvent tous être décidés par des circuits de taille polynomiale est encore ouverte. Dans cet exposé, nous verrons comment répondre à cette question sous une hypothèse de complexité de Kolmogorov, à savoir la symétrie de l'information en temps polynomial. Dans un premier temps, nous montrerons le résultat inconditionnel suivant : pour toute constante c, il existe des problèmes décidables en temps exponentiel mais pas par des circuits de taille n^c (il s'agit d'une autre preuve d'un résultat de Homer et Mocas de 1995). Puis nous verrons comment modifier la construction pour que l'hypothèse de symétrie de l'information permette une diagonalisation sur tous les circuits de taille polynomiale.

transparents

Schémas d'augmentation universels pour la navigabilité : franchir la barrière √n
Emmanuelle Lebhar (LIAFA, Paris)

Les graphes augmentés ont été introduits dans le but d'analyser le phénomène des "six degrés de séparation" observé expérimentalement par le sociologue Stanley Milgram dans les années 60. Formellement, un graphe augmenté est une paire (G, φ) où G est un graphe et φ une collection de distributions de probabilités φ_u, pour u dans V(G). A chaque noeud u de V(G), on attribue un lien suplémentaire, appelé raccourci, qui pointe sur un noeud v, appelé contact longue distance de u. La destination v de ce lien est choisie aléatoirement de la façon suivante : Pr{le contact longue distance de u est v} = φ_u(v).Dans les graphes augmentés, le routage glouton est le processus de routage sans mémoire où chauqe noeud intermédiaire choisit, parmi tous ses voisins (locaux ou longue distance), celui qui est le plus proche de la cible selon les distances mesurées dans le graphe sous-jacent G, et lui tranmet le message à router. Grossièrement, les graphes augmentés servent à modéliser la structure des réseaux sociaux, tandis que le routage glouton sert à modéliser la procédure de recherche observée dans l'expérience de Milgram.

Notre objectif est de concevoir des schémas d'augmentations universels efficaces, i.e. des schémas d'augmentation qui attribuent à tout graphe G une distribution de probabilités φ telle que le routage glouton dans (G, φ) soit rapide. Il est connu que le schéma uniforme φ_unif est un schéma qui garantit, pour tout graphe de n noeuds, un routage glouton en au plus O(√n) pas en espérance dans (G, φ_unif ). Notre résultat principal est la conception d'un schéma d'augmentation universel φ tel que le routage glouton dans (G, φ) soit en au plus Õ(n^1/3) pas en espérance pour un graphe G de n noeuds. Nous montrons également que, dans un modèle plus restrictif, la barrière √n ne peut pas être franchie.

Travail en commun avec Pierre Fraigniaud, Cyril Gavoille, Zvi Lotker et Adrian Kosowski.

transparents

Calcul du permanent
Muhammad Mumtaz Ahmad et Uffe Flarup

Muhammad Mumtaz Ahmad, actuellement en stage de M2, nous présentera l'algorithme de Barvinok pour le calcul du permanent. L'évaluation d'un permanent est un problème en général difficile (#P-complet, et VNP-complet dans le modèle de calcul algébrique de Valiant). L'algorithme de Barvinok permet cependant d'évaluer en temps polynomial le permanent d'une matrice de rang (au sens de l'algèbre linéaire) borné par une constante.

On connaît une autre famille de matrices dont les permanents sont faciles à évaluer, à savoir les matrices d'adjacences des graphes planaires (avec des poids sur les arêtes). On ne verra pas aujourd'hui la présentation de cet algorithme, mais Uffe Flarup nous présentera une construction très simple qui montre que tout polynôme peut s'exprimer comme permanent d'une matrice de ce type. Il n'est en revanche pas clair que tout polynôme puisse s'exprimer comme permanent d'une matrice de rang borné.

Aléatoire et incompressibilité
Laurent Bienvenu (LIF Marseille)

La complexité de Kolmogorov d'un objet x est la plus petite taille d'un programme qui permet de générer cet objet. Un tel plus petit programme est souvent vu comme la meilleure compression possible de x. Mais, la complexité de Kolmogorov n'étant pas calculable, il n'existe pas de procédé effectif pour réaliser cette "compression". La théorie de la complexité de Kolmogorov est donc plus une théorie basée sur la décompression que sur la compression. Dans cet exposé, nous partirons de ce constat pour réexaminer les notions classiques de l'aléatoire (suites aléatoires de Martin-Löf, suites aléatoires de Schnorr, dimension de Hausdorff effective...) en se basant sur la notion de compression.

Parameterized complexity
Uffe Flarup (Danemark)

Fixed parameter tractability has become an increasingly popular research area in the last decade. It provides an alternative framework to deal with NP-complete problems.

Classically, the running time of algorithms are most often analysed with respect to the size of the input. In parameterized complexity the analysis of running time is done with respect to two variables: size of input and size of "some parameter".

The parameter denotes a certain part of the instance and the exponential blowup in the running time is isolated solely to depend on the size of the parameter. For many "real life" applications the parameter is small (and instances large) in which case we obtain efficient algorithms. In this talk we give an overview of parameterized complexity, including examples of parameterized algorithms, the formal definitions and parametric intractability.

transparents

Complexité de Kolmogorov en temps borné
Andrei Romashchenko

Problèmes indécidables sur les automates temporisés
Olivier Finkel

Depuis que R. Alur et D. Dill ont introduit en 1994 le modèle de base des automates temporisés, cette théorie s'est beaucoup et rapidement développée et a trouvé de nombreuses applications pour la spécification et la vérification de programmes où le temps écoulé est une donnée importante. C'est le cas de nombreux systèmes réels. De nombreuses questions relatives aux problèmes de décision pour les automates temporisés ont été posées par S. Tripakis (2003) et par E. Asarin (2004). On montrera que de nombreux problèmes sont indécidables, en reduisant à ceux ci le problème de l'universalité pour les automates temporisés, qui est lui-même indécidable. En particulier on ne peut pas décider si un automate temporisé est équivalent à un automate temporisé déterministe, ni si le complémentaire d'un langage régulier temporisé est aussi régulier. Le problème de la minimisation du nombre d'horloges d'un automate temporisé est aussi indécidable. Dans le cas des automates de Büchi temporisés acceptant des mots infinis temporisés, certains de ces problèmes sont hautement indécidables, ie situés au-delà de la hiérarchie arithmétique.

Langton's Fly
Anahí Gajardo (Chili)

Le titre fait allusion à la fameuse fourmi que Cris Langton a définie dans les années 80 et qui a été particulièrement citée comme exemple de système "imprévisible". La fourmi est un automate abstrait qui se promène sur une grille carrée (bi-dimensionnelle).

Aujourd'hui il s'agit d'étudier un automate sur la grille cubique. Dans l'exposé on propose une formalisation générale d'un tel automate et on étudie les cas les plus simples. Dans ces cas on trouve qu'il y a un certain nombre de règles de comportement qui sont équivalentes, et que toutes les règles ont des forts points en commun.

Problèmes algorithmiques en théorie combinatoire des groupes libres
Pascal Weil, LaBRI (CNRS et Université de Bordeaux)

Les éléments du groupe libre F(A) engendré par un alphabet A peuvent être vus comme les mots réduits écrits sur l'alphabet symétrisé A ∪ A (un mot est réduit s'il ne contient pas de facteur aa ou aa). Les sous-groupes de type fini de F(A) peuvent être représentés de façon canonique par certains automates finis sur l'alphabet A : l'étude des groupes libres de rang fini constitue donc un champ d'application particulièrement séduisant des outils et des méthodes de l'informatique théorique et de l'algorithmique.

Durant l'exposé, je discuterai des algorithmes de construction de l'automate représentant un sous-groupe de F(A) et de certains problèmes combinatoires et algorithmiques particuliers, notamment (selon le temps disponible) :

• la conjecture de Hanna Neumann sur le rang de l'intersection de deux sous-groupes de rang fini ; et
• la complexité du problème de minimisation de Whitehead. Dans ce problème, un élément u (resp. un sous-groupe de type fini H) est donné et il s'agit de trouver parmi ses images par un automorphisme de F(A), une image de taille minimale.

transparents

Approximation polynomiale de fonctions continues et nombres flottants
Sylvain Chevillard (équipe Arénaire, ENS Lyon)

Pour calculer des valeurs approchées numériques des fonctions mathématiques usuelles, on remplace généralement la fonction par une autre, très proche et plus facile à calculer. Ainsi, l'élaboration d'un algorithme numérique pour évaluer la fonction suit généralement les étapes suivantes :

1. on détermine sur quel intervalle on souhaite évaluer la fonction ;
2. on détermine avec quelle précision on souhaite connaître les valeurs de la fonction ;
3. on cherche un approximant fournissant la précision requise sur l'intervalle choisi ;
4. on cherche un bon algorithme pour évaluer l'approximant.

Pour la troisième étape, on choisit généralement un polynôme (notamment parce que la quatrième étape a été très bien étudiée dans le cas où l'approximant est un polynôme et on sait la traiter de manière satisfaisante).

Les coefficients du polynôme doivent être stockés dans la mémoire de l'ordinateur et doivent donc être représentables sous forme de nombres-machine. Nous nous intéressons au problème de la recherche d'un très bon polynôme à coefficients représentables en machine, pour approcher une fonction continue. En utilisant la théorie des réseaux de points (et l'algorithme LLL de A. Lenstra, H. Lenstra et L. Lovász, que nous présenterons au cours de l'exposé) nous proposons un algorithme permettant d'obtenir un tel polynôme. Nous illustrerons les avantages et les défauts de l'algorithme sur un exemple complet.

transparents

Une expression de taille polynomiale en n de la factorielle d'un nombre de n chiffres
Bruno Poizat (Université Lyon 1)

Nous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions, des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient ; nous en déduisons l'existence d'un circuit de complexité 72n², calculant le coefficent binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 20n+1 calculant la factorielle d'un nombre de n chiffres. La présence de 2n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. Il est peu probable, ou du moins peu souhaitable, que l'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers. Néanmoins nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques ; cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE.

Complexité de Kolmogorov: suite du cours introductif
Andrei Romashchenko

Deux applications de la complexité de Kolmogorov :

• sur les automates finis à k têtes
• la construction, pour tous α < β rationnels, d'un mot infini ne contenant pas de sous-mot à la puissance β mais en contenant un à la puissance α.

transparents

Programmation linéaire et complexité en requêtes
Vincent Nesme (LRI, Orsay)

Je parlerai de la complexité en requêtes des problèmes suffisamment symétriques. On a alors suffisamment peu de paramètres pour pouvoir analyser exactement et de façon relativement claire les algorithmes non-adaptatifs, et ce au moyen de la programmation linéaire. Il s'agit en réalité d'un cas particulier du principe de Yao. Je parlerai un peu du rôle de la non-adaptativité, en montrant que des généralisations simples de la méthode touchent à des problèmes ouverts en théorie des graphes.

Universal reversible cellular automata
Kenichi Morita (Université d'Hiroshima)

Kolmogorov complexity and the meaning of information quantities
(cours introductif)
Andrei Romashchenko

In the theory of Kolmogorov complexity we constantly deal with several standard informational quantities, such as the mutual information, the conditional complexity, etc. We shall discuss the "physical meaning" of these quantities and some funny applications of Kolmogorov complexity. On pourra organiser un approfondissement pendant un groupe de travail ultérieur s'il y a des gens que ça intéresse.

transparents

Introduction aux algorithmes de la géométrie algébrique réelle
Marie-Françoise Roy (IRMAR, Université de Rennes 1)

Étudier les racines réelles des polynômes, décider si un ensemble défini par des inégalités polynomiales est vide, calculer ses invariants topologiques, donner des certificats de positivité, tels sont quelques uns des principaux problèmes algorithmique de la géométrie algébrique réelle. L'exposé consistera en une introduction à ces problèmes, aux méthodes existantes pour les résoudre et aux résultats actuels de complexité connus.

Variantes linéaires et NP-complètes de partitionnement d'hypergraphes
Laurent Lyaudet

On s'intéresse à la complexité de la variante suivante de partitionnement d'hypergraphes, notée P_l^k : étant donnés un hypergraphe et l tailles de couleurs dont la somme égale le nombre de sommets de l'hypergraphe, peut-on colorier ces sommets avec les l couleurs de sorte que chaque hyperarête voie au plus k couleurs ? Je montrerai que la complexité du problème P_l^k peut varier largement en fonction de la sous-classe d'hypergraphes sur laquelle on travaille et des paramètres l et k.

Robustesse dans les réseaux de régulation
Sylvain Sené

Nous donnerons des indications sur l'impact des principales sources de perturbation dans les réseaux de régulation. Nous discuterons de trois différentes sources d'influence : les conditions de bord, les méthodes de mise à jour et les variations topologiques.

Je définirai dans un premier temps les notions de bordure et de centre d'un réseau pour montrer que les changements structurels des bordures ont des effets significatifs sur le centre des réseaux. J'analyserai ensuite le rôle du mode de mise à jour sur l'asymptotique des réseaux. Enfin, je présenterai l'influence des changements topologiques sur la dynamique des réseaux.

Reconnaissance de langages sur automates cellulaires : les voisinages et leur enveloppe convexe
Victor Poupet

Je présenterai le résultat principal obtenu en collaboration avec Martin Delacourt pendant son stage de fin d'année. Après avoir rapidement redéfini les automates cellulaires en dimension quelconque, les voisinages et la reconnaissance de langages sur ces automates je présenterai la notion de temps réel en fonction d'un voisinage V, qui correspond informellement à la plus petite fonction de temps telle qu'un automate cellulaire fonctionnant sur le voisinage V puisse lire toutes les lettres du mot qu'il a reçu en entrée.

Nous verrons alors que, de manière assez surprenante, il est possible de reconnaître en temps réel sur tout voisinage V les mêmes langages que sur l'enveloppe convexe de V (c'est-à-dire même quand le voisinage V a des « trous »). Nous verrons même que tout calcul qu'il est possible de réaliser sur l'enveloppe convexe de V en un temps t supérieur au temps réel sur V peut être réalisé en temps exactement t sur V également. Notons que la réciproque est inconnue (savoir si un langage reconnu en temps réel sur V l'est également sur l'enveloppe convexe de V).

Conservation de l'information par des automates cellulaires probabilistes sur Z²
Andrei Romashchenko

We call faulty cellular automaton a probabilistic CA such that at every step and for every cell, with a high probability (1-ε) some fixed deterministic transition rule is applied. This is a model of a « faulty » computational device, where every basic element can make a mistake with a small probability ε>0.

We will discuss how to choose a deterministic rule for a 2D CA so that the corresponding faulty automaton has a stable behaviour (if the probability of a fault ε is small enough). More specifically, we construct an automaton which preserve the initial data for a long (or even infinite) time, in spite of random perturbations.

All the constructions are based on results of A.Toom and P.Gacs.

Binomial Tree topology for scalable, deterministic and robust group management
Maurice Tchuente

We show that the binomial tree topology is well suited for scalable deterministic and robust group management by exhibiting efficient procedures for decentralized construction, replacement of failed elements and routing. Concerning particularly the communication criteria, we address the conjecture which says that the binomial tree is the spanning tree of the hypercube with minimum mean distance between nodes. More precisely, we exhibit a class of transformations which can be used to prove the conjecture for small values of n and for which the binomial tree is a local minimum for all values of n.

Automates à galets
Jacques Mazoyer

Un seuil de Θ(log log n) sur la dimension doublante pour la navigabilité des graphes augmentés
ou « On ne peut pas tout petit-mondiser »
Emmanuelle Lebhar

Kleinberg a montré comment augmenter les grilles par des liens aléatoires de façon à ce qu'elles deviennent navigables; c'est-à-dire que le routage glouton calcule des chemins de longueur polylogarithmique en espérance entre toute paire de noeuds. Cela conduit à la question cruciale de déterminer si une telle augmentation est possible pour tout graphe. Dans cet article, nous répondons négativement à cette question en exhibant un seuil sur la dimension doublante, au-dessus duquel une famille infinie de graphes ne peut pas être augmentée pour devenir navigable, quelle que soit la distribution de liens. Précisément, il était connu que les graphes de dimension doublante au plus O(log log n) sont navigables. Nous montrons que pour une dimension doublante ›› log log n, une famille infinie de graphes ne peut être augmentée pour devenir navigable. Notre preuve repose sur un argument combinatoire. Enfin, nous complétons notre résultat en étudiant les grilles que nous démontrons pouvoir toujours être augmentées pour devenir navigables.

Versions algébriques de P=NP ?
Pascal Koiran

L'exposé sera consacré à deux versions algébriques de P=NP ?: celle de Valiant, dans laquelle on évalue des polynômes, et celle de Blum-Sub-Smale, dans laquelle on on s'intéresse au contraire à des problèmes de décision. On présentera notamment des tentatives de relier ces deux approches (travail en cours avec Sylvain Périfel).

transparents

Synchronization of a bounded degree graph of cellular automata with non uniform delays
in time D ⌊log_m(D)⌋
Serge Grigorieff

Note : D est le délai total, ie la somme des délais entre les cellules (au moins 1 entre des cellules voisines). La synchronisation est aussi connue sous le nom du firing squad.

Bornes inférieures pour des problèmes de diamètre
Hervé Fournier

Le diamètre d'un ensemble P de n points de R^d est le maximum de la distance euclidienne entre deux points de P. Si P est l'ensemble des sommets d'un polytope en dimension 3, et si on donne en plus la structure combinatoire de ce polytope, on montre que décider si le diamètre de P est supérieur à 1 nécessite une profondeur n log(n) dans le modèle des arbres de calcul algébrique. Ceci montre que l'algorithme de Ramos pour calculer le diamètre d'un polytope de dimension 3 est optimal. On donne aussi une réduction en temps linéaire du problème de Hopcroft d'incidence entre points et droites de R² au problème du diamètre en dimension 7.

transparents

Stratégie d'encerclement connexe dans les graphes
Nicolas Nisse

Étant donné un graphe dont les arêtes sont contaminées, une stratégie d'encerclement permet à un ensemble d'entités mobiles de « nettoyer » ce graphe. Une autre facon de voir le problème est de considérer un graphe dans lequel circule un intrus que l'on doit capturer. Le but de ce séminaire est de présenter l'étude des stratégie d'encerclement dans les graphes. Nous verrons les motivations liées à d'autres problèmes issus de la théorie des graphes et listerons également quelques uns des principaux résultats liés à ce problème. En particulier, nous étudierons les stratégies d'encerclement dites connexes et nous présenterons le lien entre ce problème et les décompositions arborescentes.

transparents

Transitoire de longueur exponentielle
généré par une équation neuronale récurrente
René Ndoundam

Ceci est un travail en collaboration avec Maurice Tchuente.

Nous étudions les suites générées par les équations neuronales récurrentes de la forme x(n) = sign(∑_j=1..k a_j x(n-j) -θ), où k est la taille de la mémoire (k représente le nombre d'états précedents x(n-1), x(n-2), ..., x(n-k) qui interviennent dans le calcul de x(n)). Nous sommes interessés par la longueur du transitoire.

Nous montrons que sous certaines hypothèses, il est possible de construire une équation neuronale de taille mémoire (s+1)6m dont la dynamique contient une évolution dont la longueur du transitoire est (s+1)(3m+1+ppcm(p₀, p₁, ..., p_s-1, 3m-1)) et un cycle de longueur (s+1)ppcm(p₀, p₁, ..., p_s-1), où ppcm désigne le plus petit commun multiple et p₀, p₁, ..., p_s-1 sont les nombres premiers compris entre 2m et 3m.

transparents

Le show des thésards, 2^e partie
Damien Regnault, Sylvain Périfel, Vincent Nesme

Une brochette de thésards présenteront de manière relativement élémentaire des problèmes, des questions ouvertes (ou pas) en rapport avec leurs travaux (ou pas).

Damien Regnault : la règle antimajorité en 2D et 8 voisins, en dynamique asynchrone.

Syvain Périfel : circuits pour calculer des polynômes.

Vincent Nesme : Tactique quantique en kit (borne inférieure de temps de calcul).

Le show des thésards, 1^re partie
(par ordre d'apparition) Laurent Lyaudet, Florent Becker, Jean-Baptiste Rouquier, Victor Poupet

Laurent Lyaudet présentera l'état des connaissances sur la conjecture du second voisinage de Seymour. Cette conjecture stipule que, dans tout graphe orienté fini, il existe un sommet dont le second voisinage est moins aussi gros que le premier voisinage.

Florent Becker et Jean-Baptiste Rouquier proposeront d'étudier des automates cellulaires particuliers, agissant sur les cellules d'un pavage du plan par des calissons.

Pour conclure, Victor Poupet présentera brièvement un problème de réécriture : quand est-ce que la règle 0^p1^q → 1^r0^s termine-t-elle ?

Quelques remarques sur les facteurs de graphes
Martín Matamala

Soit λ ∈ ]0;1[. Nous montrons que tout graphe G=(V,E) admet un λ-facteur : un sous-graph couvrant G'=(V,F) tel que ∀v∈V  deg_F(v) - λdeg_E(v) ≤1. (deg_F(v) est le nombre d'arcs de F incidents à v).

Pour toute fonction w: E→ [0,∞[ nous montrons aussi qu'il existe un λ-facteur valué, dans le sens suivant :

où M(v) = max{w_e | e∈δ(v)}. Nous présentons finalement une nouvelle caractérisation des (g,f)-facteurs.

En collaboration avec José R. Correa, School of Business, Universidad Adolfo Ibáñez, Santiago, Chili.

Largeur arborescente et largeur de branche dans les graphes
Fréderic Mazoit

Puissance des gros produits
Sylvain Périfel

Dans notre modèle de calcul à la Valiant , on dit qu'une famille de polynômes est facilement calculable si elle se calcule par une famille de circuits arithmétiques de taille polynomiale (n'ayez crainte, je commencerai par les bases).

On s'intéresse alors à la puissance de gros produits : soit VπP (ou vipaillepi) la classe des polynômes qui sont des produits exponentiels de polynômes facilement calculables. Je propose d'étudier pourquoi ces gros produits ne semblent pas eux-mêmes facilement calculables : je montrerai en particulier quelques liens avec les classes P et NP (booléennes ou algébriques). Les techniques utilisées vont de la simulation de circuits booléens à la séparation d'hyperplans, saupoudré d'un soupçon de géométrie algébrique élémentaire.

Sur la complexité des langages de mots infinis acceptés par machines finies
Olivier Finkel

On considère l'acceptation de mots infinis par des machines finies avec les conditions usuelles de Büchi ou de Muller. L' ensemble des mots infinis sur un alphabet fini Σ est naturellement muni de la topologie usuelle de Cantor. L'ensemble des Boréliens de cet espace topologique est alors defini à partir de l'ensemble des ouverts par opérations successives d'unions et d'intersections dénombrables. On montrera alors le résultat surprenant suivant. Du point de vue de la complexité topologique des langages acceptés, en considérant la hiérarchie Borélienne, la hiérarchie projective qui l'étend, et la hiérarchie de Wadge qui est un raffinement de la hiérarchie Borélienne, un automate à un compteur suffit à obtenir toute la complexité d'une machine de Turing. De la preuve de ces résultats on déduira que de nombreux problèmes de décisions classiques, comme le problème de l'universalité, de l'inclusion, ou de l'égalité, pour les ω-langages algébriques ou à un compteur sont hautement indécidables, et sont situés au niveau π¹₂ dans la hiérarchie analytique.

Reliable computations with non-reliable components
Andrei Romashchenko

In most usual models of computations, if at least one step of an algorithm (e.g., a Turing machine, a cellular automaton, a boolean circuit, etc.) is faulty, then the final result of the whole computation is most probably corrupted. Can we implement reliable computations assuming that the used components are non-reliable and each elementary step can be corrupted with some probability? This problem was investigated by many authors. It was proved that for several natural models (boolean circuits, clocked networks, cellular automata) the answer to this question is positive : relative computations can be implemented on faulty components; moreover, the price for reliability, i.e., the required blow-up of the memory and slow down, is quite modest.

I will five a brief survey of known results (J. von Neumann, A. V. Kuznetsov, N. Pippenger, D. Speilman, P. Gacs) and talk about some useful technique employed in this area. Also I plan to discuss a few open questions.

Liens entre la complexité descriptive et la complexité algorithmique dans le cadre de la reconnaissance de langages sur automates cellulaires
Victor Poupet

Parmi les questions qui se posent en reconnaissance de langages sur automates cellulaires (AC), l'une d'entre elles est particulièrement simple : les langages reconnus par un AC en temps-réel (exactement la longueur du mot) sont-ils les mêmes que ceux reconnus en temps linéaire ? Même mieux : Les langages reconnus en temps-réel sont-ils les mêmes que ceux reconnus en espace linéaire (et temps quelconque) ? Bien que très simples, ces deux questions sont toujours ouvertes. Afin d'approcher le problème sous un angle différent (avec le secret espoir de faire avancer le problème) j'introduirai une notion de complexité descriptive, un peu similaire à la complexité de Kolmogorov mais avec quelques contraintes supplémentaires de telle sorte qu'elle soit calculable. Puis, en utilisant certaines propriétés des langages reconnus en temps réel vis-à-vis de cette complexité, je montrerai comment on peut obtenir des résultats de séparation de classes (au sens de la complexité algorithmique) à partir de résultats sur la complexité descriptive. Je parlerai aussi rapidement si j'ai le temps de ce que l'on peut obtenir avec cette méthode dans le cas Turing (mais il n'y a rien de bien transcendant pour le moment).

Influence de l'asynchronisme sur les automates cellulaires élémentaires
Damien Régnault

Le but est d'analyser le comportement asynchrone des automates cellulaires. Les automates cellulaires sont utilisés pour modéliser des systèmes composés d'un grand nombre d'éléments interagissant ensembles (agents en économie, particules en physique, protéines en biologie, systèmes distribués...). Les automates cellulaires ont été largement étudiés en régime synchrone alors que ces systèmes évoluent de façon asynchrone. Les études de H. Fuks et B. Schönfisch ont montré en étudiant des cas particuliers que le comportement des automates cellulaires pouvait être radicalement différent en introduisant de l'asynchronisme dans leur fonctionnement. Récemment, Gacs a prouvé l'indécidabilité de déterminer pour un automate donné si la séquence des états pris par une cellule donnée est indépendante de l'historique des mises à jour.

Nos travaux se situent dans la continuation de ceux de Nazim Fatès. Il s'est intéressé au temps de relaxation des automates cellulaires en régime asynchrone. Le temps de relaxation étant le temps nécessaire pour qu'une configuration donnée atteigne un état stable (dans les cas que nous traiterons ici, il s'agira essentiellement de points fixes). Le temps de relaxation nous permet donc de savoir le temps nécessaire pour qu'une simulation prenne en compte tous les phénomènes propre à un automate. Le régime asynchrone choisi étant un modèle probabiliste où à chaque étape, chaque cellule a une certaine probabilité donnée de se mettre à jour. Nous avons mené une étude exhaustive de cas sur la classe des automates cellulaires élémentaires doublement quiescents. Je présenterai nos résultats ainsi que les outils que nous avons utilisés pour étudier ces phénomènes.

Sous-shift associé à une machine de Turing
Anahi Gajardo (Université de Conception, Chili)

On étudie les machines de Turing en tant que système dynamique. Pour cela, on considère qu'elles démarrent avec un mot initial infini, et qu'elles ne s'arrêtent pas.

À une machine donnée, on associe le sous-shift correspondant aux séquences des lettres lues, et des états internes que la machine a au cours du temps. On montre des propriétés générales de ce sous-shift, ainsi que le rapport entre certaines propriétés de la machine et celles de son sous-shift associé.

Propagation de l'information et entropie strictement positive des automates cellulaires à une dimension
Pierre Tisseur

Pour des automates cellulaires de dimension D, nous établissons des liens entre la vitesse de propagation de l'information et une variante de l'entropie métrique de ces automates. Cette nouvelle variante de l'entropie métrique correspond à la définition standard dans le cas des automates cellulaires unidimensionnels. Dans ce dernier cas il est aussi possible d'établir une égalite entre l'entropie de l'automate, le flux de l'information et l'entropie du shift.

Débits extrémaux dans les réseaux de Petri
Anne Bouillard

Dans cet exposé, je parlerai du débit dans les réseaux de Petri à choix libres vivants bornés, routés et temporisés. Dans une première partie, après avoir défini la notion de débit dans les réseaux temporisés, je montrerai comment calculer ce débit pour des routages périodiques et trouver les routages qui donnent les débits extrémaux (minimal et maximal) pour des temporisations rationnelles. Dans une deuxième partie, je montrerai comment calculer le débit minimal pour des réseaux à choix libres 1-bornés. La méthode utilisée montre que le routage permettant d'atteindre ce débit est périodique de petite période.

Un vecteur orthogonal à environ la moitié d'une famille de vecteurs
Sylvain Perifel

Lorsque l'on a des polynômes à plusieurs indeterminées et à coefficients entiers, leur évaluation en un vecteur réel donne l'ensemble des signes des images de ce vecteur. Bien entendu, ces ensembles de signes peuvent différer selon les points. Pour distinguer deux points selon ce critère, on peut calculer leurs images par tous les polynômes, et comparer les signes. Cependant, on souhaite réduire le nombre de tests  ainsi, sous l'hypothèse que les tests sont des polynômes facilement calculables, on deduira que des problèmes difficiles sur les réels deviennent faciles.

Des travaux antérieurs donnent déjà des tests à effectuer pour différencier nos points, mais ces tests sont de complexité inconnue : pour pouvoir prendre en compte l'ordre <, on passe en effet par un joli lemme de dimitri grigoriev, non constructif. il s'agit de trouver un vecteur sur z/2z qui soit orthogonal à environ la moitié d'une famille de vecteurs donnés. j'expliquerai un algorithme pour trouver ce vecteur.

Quelques propriétés des systèmes de numération abstraits construits sur un langage régulier
Michel Rigot

Lorsqu'on étudie les systèmes de numération du point de vue de la théorie des langages formels, une question apparaissant naturellement est de déterminer quels ensembles d'entiers donnent lieu à un ensemble de représentations qui forme un langage régulier (ou rationnel), c'est-à-dire accepté par un automate fini. On parle dès lors d'ensembles reconnaissables d'entiers. Par exemple, les nombres pairs et les puissances de 2 sont trivialement reconnaissables pour le système binaire.

Au lieu de prendre un système à base entière, une première généralisation consiste à considérer une suite strictement croissante d'entiers et de l'utiliser pour décomposer au moyen de l'algorithme d'Euclide (ou algorithme glouton) n'importe quel entier. La notion d'ensemble reconnaissable d'entiers se transpose alors aisément à ce cadre. Il est en outre bien connu que la régularité de l'ensemble des représentations de tous les entiers dépend de la suite considérée (résultats de J. Shallit, M. Hollander et N. Loraud). Il paraît cependant naturel -- ne serait-ce que pour vérifier « simplement » si un mot écrit sur l'alphabet des chiffres est bien la représentation d'un entier calculée par l'algorithme d'Euclide -- de demander que cette dernière propriété de régularité soit satisfaite.

Pour répondre à cette dernière requête, il est possible de procéder différemment et d'introduire la notion de système de numération abstrait (notion introduite par Pierre Lecomte et moi-même, il y a environ 5 ans). Considérons un langage régulier infini L écrit sur un alphabet totalement ordonné (A,<). enumérer les mots de l par ordre généalogique croissant (c'est-à-dire, par longueur croissante et au sein d'une longueur, en utilisant l'ordre du dictionnaire induit par l'ordre total sur a) fournit une bijection entre les entiers non négatifs et les mots de l. on dira que le (n+1)-ième mot de l est la s-représentation de n, si s=(l,a,<) est le système de numération abstrait considéré. on dira qu'un ensemble d'entiers est s-reconnaissable si les s-représentations de ses éléments forment un langage régulier.

Cette manière de procéder généralise les systèmes classiques de position comme les systèmes à base entière ou encore le système de Fibonacci. On peut donc se poser les mêmes questions et introduire les mêmes concepts que dans le cadre classique : ensembles reconnaissables d'entiers, suites automatiques, représentations des nombres réels, périodicité des représentations, étude de fonctions sommatoires, problèmes de pavage, etc... Bien évidemment, c'est l'occasion d'observer des phénomènes n'apparaissant dans le cadre classique (en particulier, un système abstrait n'est en général pas un système de position).

Dans cet exposé, en guise d'introduction, je brosserai à grands traits les résultats classiques concernant les systèmes de numération de position et le caractère reconnaissable d'ensembles d'entiers (caractérisation logique, théorème de Cobham, ...). Ensuite, je présenterai la notion centrale de système de numération abstrait et développerai certaines questions : préservation du caractère reconnaissable d'un ensemble d'entiers après multiplication par une constante, reconnaissance d'ensembles particuliers (image de polynômes, etc...). Enfin, je montrerai comment représenter les nombres réels dans un tel système au moyen de mots infinis sur A.

Divers préprints sont disponibles sur ma page : http://www.discmath.ulg.ac.be/

Les pavages auto-assemblants
Florent Becker

Les pavages auto-assemblants sont un modèle de calcul introduit par Winfree afin de modéliser des processus d'auto-assemblage, par exemple dans l'ADN. On se donne un jeu de tuiles de Wang, c'est à dire des carrés avec des côtés colorés, dont les côtés sont badigeonnés de colle. On observe alors la croissance d'un motif suivant la régle d'évolution suivante : une tuile peut venir s'ajouter au motif si les couleurs de ses côtés correspondent à celles d'un emplacement libre et si la somme des colles mises en jeu est suffisante.

A partir de ce modèle, nous étudierons quelques constructions simples (carrés, triangle de Sierpinsky) dûes à Winfree et Rothemund, et les différentes notions d'efficacité que l'on peut rechercher : taux de parallélisme, résistance aux erreurs ...

Ensuite, nous verrons le rôle particulier que jouent les homothéties dans ce modèle, et leur lien avec le temps dans les modèles plus classiques.

Codes parfaits sur la poutre
Paul Dorbec (IMAG)

La domination est l'un des problèmes classiques de la théorie des graphes. Le problème dual de la domination est celui des empilements, et a été étudié dans le cadre de la théorie des codes correcteurs d'erreurs. Un code parfait dans un graphe est un code qui est aussi un dominant. Si le graphe est suffisamment régulier, ce code parfait est un pavage du graphe. Golay et Hamming ont caractérisé l'existence de codes binaires parfaits. Ces codes correspondent à des pavages sur l'hypercube. Golomb et Welsh ont eux étudiés les codes parfaits dans la métrique de Lee, c'est-à-dire des codes parfaits sur les grilles n-dimensionnelles. Au cours de cet exposé, nous étudierons une généralisation commune de ces codes. Nous verrons quelques résultats proposés récemment sur l'existence de codes parfaits dans le produit cartésien d'une grille et d'un hypercube.

Robust simulations of Turing machines with analytic maps and flows
Daniel Garca (LORIA)

In this talk, we will show that analytic maps can simulate Turing machines in an error-robust manner. The proof will be constructive, and each map will only require a finite number of the usual real functions (polynomials and trigonometric functions). We will then extend this result to the continuous-time case using systems of ordinary differential equations. All simulations will be carried in real time. The talk describes joint work with M. L. Campagnolo and J. Buescu.

Étude des graphes planaires cofinis selon leurs groupes de symétries
David Renault (LaBRI)

Les graphes cofinis constituent une famille de graphes possédant un groupe de symétries (ou automorphismes) non trivial, comme c'est le cas pour les graphes de Cayley et les graphes sommet-transitifs. Lorsque ces graphes sont de plus planaires, ces symétries peuvent se traduire de manière simple gràce à des symétries du plan dans lequel les graphes sont plongés. L'ensemble de ces symétries permet alors de décrire globalement le graphe à l'aide de données géométriques locales, par des structures appelées schémas d'étiquetages.

Nous étudions les groupes de symétries et les schémas d'étiquetage des graphes planaires cofinis possédant une représentation topologique simple : les graphes planaires topologiquement localement finis. Les plongements de ces graphes planaires peuvent être vus comme des pavages du plan, pouvant posséder des faces finies ou infinies. Nous montrons comment les schémas d'étiquetage permettent de caractériser le graphe et ses plongements. Ce travail permet d'énumérer cette famille de graphes planaires cofinis, en particulier lorsqu'ils sont de Cayley ou sommet-transitifs.

Cette étude permet de s'intéresser à la géométrie des graphes et à la structure de leurs groupes d'automorphismes. En particulier, il est possible de s'intéresser à des problèmes de théorie combinatoire des groupes, comme le problème du mot généralisé. Les problèmes de décidabilité de la logique permettent de classifier ces graphes en deux grandes familles, selon leur largeur arborescente et la géométrie de leur plongement.

Algorithmes sur les groupes de permutations et les graphes
Vincent Nesme

J'introduirai le concept de groupe de permutations et presenterai quelques algorithmes (classiques !) assez generaux. Le but est de montrer que, etant donné un graphe dont les noeuds sont colories de telle maniere que les classes de couleur sont de taille bornee, decider s'il existe un automorphisme du graphe non trivial ne changeant pas la couleur des noeuds est dans P.

L'universalité dans les automates cellulaires : miracle ou banalité ?
Guillaume Theyssier

Quelle est la densité des automates cellulaires universels ? Cette intrigante question a semble-t-il été posée pour la première fois par Conway puis reformulée notamment par Wolfram (16ème problème de Twenty problems in the Theory of Cellular Automata, puis comme conséquence du Principle of Computational Equivalence dans A New Kind of Science). Nous ne répondons pas à la question. Cependant nous présentons une famille d'automates cellulaires naturelle (et définie localement) pour laquelle les réponses à cette question et à beaucoup d'autres suivent une loi zéro-un. Nous montrons ensuite que le problème de l'universalité reste indécidable pour cette famille et exposons les conséquences de ce fait. Enfin, nous discutons des difficultés de la question générale.

Le niveau de formalisme, les prérequis et la durée de l'eposé seront adaptés en fonction de l'auditoire.

Accélération par une constante sur Automates Cellulaires fonctionnant sur des voisinages quelconques
Victor Poupet

Je parlerai de la reconnaissance de langages en temps réel sur des automates cellulaires en dimension 1, et je montrerai comment on peut obtenir un théorème d'accélération par une constante (tout langage qui est reconnu en temps réel plus une constante peut être reconnu en temps réel) pour n'importe quel (enfin presque) voisinage. Je redéfinirai les notions de base et comme la preuve est décement simple je reprendrai les choses depuis le début donc c'est facilement compréhensible par tous (sauf si je me mélange les pinceaux et que j'embrouille tout le monde, mais je vais essayer d'éviter...). Si j'ai un peu de temps je parlerai des problèmes que l'on rencontre en dimension 2 et au delà (mais malheureusement pas beaucoup de jolis résultats dans ce cas-là).

Largeur de branche des graphes de cordes
Laurent Lyaudet

Les décompositions en branches des graphes fournissent des schémas du type diviser pour régner pour résoudre certains problèmes. Néanmoins trouver un bon schéma de ce type est un problème NP-complet. C'est pourquoi, on se limite à l'étude du problème sur certaines classes de graphes. Dans mon exposé, je présenterai deux résultats permettant d'espérer obtenir un algorithme polynomial pour calculer la largeur de branche des graphes de cordes.

Bornes inférieures en calcul quantique
Vincent Nesme

Je parlerai d'un modele simple de complexite en requête quantique, donnerai quelques exemples, expliquerai la méthode pour trouver des bornes inférieures dite des polynômes et montrerai quelques applications.

La théorie de la mesure en complexité
Emmanuel Jeandel

Au lieu de s'attaquer de front à la fameuse question P=NP?, certains voudraient commencer par montrer que NP ``n'est pas trop gros'', donc essayer de définir une notion de ``taille'' pour des classes de complexité. On peut évidemment donner plusieurs sens à ce concept ; on s'intéressera ici à la notion de mesure (et de dimension) d'une classe de complexité définie par Lutz en 1987. Au lieu de se demander si P=NP, on commence donc par se demander si NP est de mesure 0.

Ce groupe de travail s'attachera à donner une introduction à la théorie de la mesure en complexité, en montrant comment les concepts de la théorie des probabilités (en particulier les martingales) se transposent dans ce contexte. On établira ensuite quelques propriétés de base de la mesure, afin de montrer finalement comment on peut déduire de l'hypothèse NP n'est pas de mesure 0 plusieurs corollaires sympathiques. On montrera en particulier (si j'ai le temps)

• NP n'est pas de mesure 0 => E != NE
• BPP est soit de mesure 0 soit de mesure 1.

L'exposé sera pédagogique, et il n'est donc pas nécessaire de connaître la théorie de la complexité ou les fondements des probabilités pour comprendre l'exposé.

Pugilat à Greifswald
Bruno Poizat (Institut Girard Desargues, Lyon 1)

Il y a au moins deux personnes dans cette petite ville de l'est de l'Allemagne qui revendiquent la solution d'un probleme pose par John B. Goode il y a dix ans. La plus convaincante est celle d'Hemmerling.

Le probleme est de trouver une structure de langage fini satisfaisant P = NP au sens de BSS, c'est-a-dire qui elimine rapidement les quanteurs. La solution est donnee par la theorie de deux successeurs s0 et s1, avec leur predecesseur p commun, et un predicat P judicieusement choisi ; l'algorithme d'elimination, pour savoir si (E y) f(a,y) est vraie , commence par demander des informations sur le voisinage du uple a qui suffisent a determiner si la formule est vraie ou non ; comme le predicat P est rare, il n'y a pas beaucoup de possibilites pour ce voisinage, qui se code par un uple booleen u de longueur polynomiale ; le predicat P , construit par une induction facile, se comporte comme un oracle permettant le calcul immediat de la valeur de verite de la formule a partir de u.

Dense triangle-free graphs are four colorable - a solution to the Erdos-Simonovits problem
Stephan Thomasse

Many results deal with the chromatic number of triangle-free graphs, and more specifically triangle-free graphs with many edges (for instance Turan's theorem is of this kind). In this context, Hajnal proved that for every epsilon>0, one can find triangle-free graphs with minimum degree >(1/3-epsilon)n with arbitrarily large chromatic number, where n is the number of vertices of the graph. His construction is based on triangle-free Kneser graphs with large chromatic number (Cf Lovasz' theorem).

But this construction cannot be extended to minimum degree >n/3, and in 1972, Erdos and Simonovits asked whether the chromatic number could be bounded in this case. They believed first that 3 could be an upper bound, but Haggkvist found a 4-chromatic, and 10-regular counter-example on 29 vertices, based on the Grotsch graph. Later on, Jin proved that minimum degree >10n/29 implies that the chromatic number is bounded by 3, and this bound is sharp with Haggkvist's example. The first bound in the general case was given by Thomassen: he proved that for every epsilon>0, the chromatic number of triangle-free graphs with minimum degree > (1/3+epsilon)n is bounded by some constant c depending on epsilon, where c goes to infinity when epsilon goes to 0.

With Stephan Brandt (Ilmenau TU), we completely solve * the problem, proving that minimum degree >n/3 implies 4-colorable. The proof uses a tiny bit of linear programming (essentialy complementary slackness).

In this talk, I will present our proof.

* Of course this is a little bit cheating since we use strict inequality, in fact we do not have any idea of what happens when the degree is precisely n/3, the answer can be anything between unbounded and 4.

Dynamique symbolique en géométrie discrète
Valérie Berthe

Forces et faiblesses de la transformée de Fourier
Vincent Nesme

Je parlerai de l'art et de la manière d'utiliser la transformée de Fourier en calcul quantique pour trouver des sous-groupes cachés. On verra que, bien qu'elle soit optimale dans nombre de cas simples, cette technique paraît pourtant totalement inadaptée dans des cas plus intéressants. Puis je parlerai des moyens de s'accomoder de cette apparente inadaptation, soit en contournant le problème, soit en rentrant dedans avec des œillères.

Sur la complexité topologique de quelques classes de langages de mots infinis
Olivier Finkel

Les omega langages rationnels sont les langages de mots infinis acceptés par automates finis avec condition d' acceptation de Büchi ou de Muller. On considerera en particulier deux extensions naturelles de ces langages :

1. les omega langages algebriques acceptés par automate à pile avec condition d' acceptation de Büchi ou de Muller.
2. les relations rationnelles infinitaires, ensembles de couples de mots infinis, reconnus par transducteurs de Büchi ou par automates de Büchi à deux rubans et deux têtes de lecture asynchrones. Une relation rationnelle infinitaire peut aussi être considerée comme un langage de mots infinis sur un alphabet produit.

Afin d'étudier la complexite de ces langages, on considère l' ensemble des mots infinis, sur un alphabet fini Σ, naturellement muni de la topologie usuelle de Cantor. L'ensemble des Boreliens de cet espace topologique est alors defini à partir de l'ensemble des ouverts par operations successives d' unions et d' intersections denombrables. Une question naturelle est alors de situer les classes d'omega langages par rapport à la hiérarchie borélienne et à la hiérarchie projective qui l'étend.

On présentera des résultats recents sur la complexité topologique des omega langages algébriques, et des relations rationnelles infinitaires : en particulier il existe des omega langages algébriques et des relations rationnelles infinitaires analytiques non boréliens. On étudiera aussi les liens avec la hiérarchie de Wadge, qui est un raffinement de la hiérarchie borélienne defini à l'aide de la notion de réduction par des fonctions continues.

Arbres binaires de recherche aléatoires
Nicolas Schabanel

Je vais vous présenter une représentation graphique des arbres binaires de recherche qui permet d'obtenir très facilement tout plein de paramètres sur ces arbres aléatoires (profondeur du i-ème noeud, proba d'existence d'un motif donné, nombre d'ancêtres, etc...). Cette présentation sera basée sur le cours de Devroye de l'école ALEA de janvier dernier.

Branchwidth des graphes d'intervalles circulaires
Frédéric Mazoit

Je montrerai que le calcul du branchwidth des graphes d'intervalles circulaires est polynômial.

Ordres cycliques pour digraphes fortement connexes, preuve d'une conjecture de Gallai.
Stéphane Bessy (LaPCS, UCBL)

En collaboration avec S. Thomassé. Une énumération d'un digraphe D fortement connexe à n sommets est une bijection entre les sommets de D et les sommets de G_n, un n-gone du plan. Un ordre cyclique est alors une classe de représentations cycliques stable par deux opérations : rotation des sommets de D sur G_n et échange de deux sommets de D consécutifs sur G_n et non reliés dans D. Ces opérations sont définies de façon à laisser invariant l'indice d'un circuit de D dans une énumération, c'est-à-dire le nombre de tours du circuit dans G_n, comptés dans le sens direct.

La définition d'équivalents cycliques pour la stabilité, le 'feedback arc set' et le nombre chromatique permet l'énoncé de trois théorèmes min-max. Le premier de ces théorèmes implique que tout digraphe fortement connexe D est couvrable par α (D) circuits, où α (D) est la stabilité de D. Ceci répond à une conjecture de T. Gallai, posée en 1963. Le dernier des théorèmes est une généralisation d'un résultat de J.A. Bondy de 1976 : tout digraphe D fortement connexe a un circuit de longueur au moins χ (D), où χ (D) est le nombre chromatique de D.

Références :

• J. A. Bondy. Diconnected orientations and a conjecture of Las Vergnas. J. London Math. Soc. (2), 14(2):277--282, 1976.
• T. Gallai. Problem 15. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 160--161. Publ. House Czechoslovak Acad. Sci., Prague, 1964.

Automates celullaires et robustesse à l'asynchronisme
Nazim Fatès

Les Automates Cellulaires (AC) sont une classe de systèmes dynamiques discrets qui sont fréquemment utilisés pour modéliser des systèmes complexes dans lesquels la dynamique est spécifiéee de façon locale. Dans leur acception classique, les AC sont simulés sur une grille régulière et avec une synchronisme parfait des transitions. Néanmoins, ces deux hypothèses ont peu de chances de représenter fidèlement ce qui se déroule à une échelel microscopique pour des systèmes physiques, biologiques ou sociaux. Nous nous interrogeons donc sur la capacité des AC à garder leur comportement lorsqu'ils sont soumis à de petites pertubrations de synchronisme. Cet exposé se concentre sur l'étude des automates cellulaires asynchrones unidimensionnels dépendants de leurs plus proches voisins. Nous définissons formellement ce que signifie ``le comportement d'un AC est robuste à l'asynchronisme'' en utilisant une approche statistique avec des paramètres macroscopiques et nous présentons un protocol expérimental qui vise à trouver quels sont les AC élémentaires unidimensionnels robustes. En conclusion, nous exminons comments les résultats exposés peuvent être utilisés pour la recherche de modèles répondant aux critères de robustesse.

Discrete Particles and Collisions Systems for Complex Cellular Automata Constructions
Nicolas Ollinger (LIF - Marseille)

We introduce discrete particles and collisions systems as a new framework to deal with complex constructions on small cellular automata. Various algorithms, necessary to represent the constructions and prove the soundness of the construction steps, are sketched. The expressiveness of our framework is compared to the tilings of the plane using Wang tiles, leading to undecidability results. Eventually, a formal proof of Cook-Wolfram's construction of the universality of rule 110 is derived.

Election et Nommage par Calculs Locaux
Jérémie Chalopin

Les calculs locaux sont des modèles de caluls distribués basés sur des réécritures de graphes. Ce formalisme permet de décrire simplement des algorithmes distribués et de prouver leur correction; il permet aussi de donner des résultats d'impossibilités en utilisant certains outils combinatoires connus.

On s'intéresse en particulier au problème de l'élection qui consiste à distinguer un unique sommet du graphe en partant d'une configuration initiale quelconque, ainsi qu'au problème du nommage qui consiste à assigner une identité distincte à tous les sommets du graphe. Dans différents modèles de calculs locaux, on caractérise quels sont les graphes pour lesquels il existe un algorithme d'élection ou un algorithme de nommage. Ces résultats nous permettent en particulier de donner une hiérarchie stricte entre les différents modèles.

Pour caractériser les graphes dans lesquels on sait élire ou nommer, on utilise deux outils fondamentaux. Le premier est le lemme de relèvement d'Angluin qui permet de donner des conditions nécessaires. Le second est l'algorithme de Mazurkiewicz, à partir duquel on peut obtenir des algorithmes permettant de donner des conditions suffisantes.

Le modèle orientation-hauteur
Arnaud Dartois

Le modèle orientation-hauteur (Height-Arrow Model) a été introduit en 1996 par V.B. Priezzhev, D. Dhar, A. Dhar et S. Krishnamurthy. Ce modèle est une généralisation du modèle du tas de sable Abelien (Sandpile Model) et du modèle du marcheur Eulerien (Eulerian Walker).

Après avoir défini formellement le modèle et posé quelques notations, nous montrerons que la théorie développée pour le modèle du tas de sable se généralise dans ce nouveau contexte. En particulier,

• nous définissons un ensemble de configurations dites récurrentes et un ensemble d'opérateurs qui forment un groupe Abelien agissant sur cet ensemble,
• nous étendons le critère de Dhar (reconnaissance d'une configuration récurrente) et l'algorithme thermique (burning algorithm) à ce contexte,
• nous construisons un ensemble de isomorphismes de groupes qui permettent de définir un ensemble d'additions naturelles pour l'ensemble des configurations récurrentes.

Langages d'images : tour d'horizon
B. Nouvel

Nous initierons cet exposé par une présentation « classique » des langages d'images. Celle-ci débutera par l'énumération des processus utiles soit à générer une image, soit à reconnaître un langage d'images. Alors nous évoquerons les principaux résultats de l'article de Giammarresi et Restivo sur la notion de rationalité pour les langages d'images. Plus généralement, nous rappellerons bien sûr la hiérarchie qui est mentionnée dans celui-ci. Puis nous discuterons un peu de la caractérisation mots points fixes de morphismes itérés. On parlera de la conjecture de Nivat. Puis nous présenterons les premiers résultats expérimentaux obtenus en cherchant à étendre la notion de graphe de Rauzy à la dimension n.

À la recherche de plus courts chemins dans les graphes à contacts distants
Emmanuelle Lebhar

Depuis l'expérience de Milgram de 1967, qui démontre que les individus trouvent efficacement des courts chemins dans de grands graphes en utilisant uniquement leur vision locale du graphe, plusieurs modèles ont été proposés pour étudier ce phénomène de petit monde.

En 2000, Kleinberg a montré que la plupart des modèles précédemments connus manquaient une caractéristique importante du phénomène : aucun algorithme décentralisé ne pouvait trouver les courts chemins lorsqu'ils existaient. Il a alors introduit un modèle composé d'une grille carrée (représentant les connaissances locales) augmentée de liens dirigés (symbolisant les contacts distants) distribués harmoniquement. Il propose de modéliser le comportement des individus par l'algorithme glouton qui passe le message au contact (local ou distant) du possesseur actuel du message qui est le plus proche du destinataire. Il montre que cet algorithme glouton calcule un chemin de longueur moyenne Θ(log²n) entre toute paire de noeuds.

Nous nous poserons la question de la pertinence du choix de la stratégie gloutonne pour modéliser les comportements sociaux. Nous proposons une nouvelle stratégie dans laquelle les noeuds consultent leurs connaissances avant de décider à qui envoyer le message. Notre algorithme présente les mêmes caractéristiques de complexité que l'algorithme original de Kleinberg : il utilise Θ(log n) bits de mémoire et visite O(log²n) noeuds. Il calcule des chemins plus courts, de longueur moyenne O(log n(log log n)²), entre toute paire de noeuds. Cet algorithme montre que consulter son voisinage conduit à des améliorations de performances, il montre aussi que cette consultation est de moins en moins utile lorsque l'on s'approche de la destination.

Calcul quantique à l'aveugle
Pablo Arrighi

Où l'on étudiera la possibilité de « faire faire quelque chose à quelqu'un, tout en empêchant cette personne de connaître la nature de la tâche qu'il exécute". Supposons le scénario suivant : Alice souhaite que Bob calcule la valeur de f au point x, mais sans que ce dernier ne connaisse la valeur de x. Ce genre de situation intervient lorsqu'Alice (la cliente), possède des ressources computationnelles plus limitées que celles de Bob (son serveur), ou bien encore lorsque Bob possède des connaissance gardées secrètes sur la structure de f. Existe-t-il un protocole forçant Bob à calculer f(x) aveuglément, c'est à dire sans observer x ? On donnera un protocole de calcul quantique à l'aveugle pour la classe des fonctions qui admettent une procédure efficace pour générer des paires aléatoires d'argument-résultat, comme la factorisation. La sécurite obtenue est inconditionelle dès lors que les lois de la physique quantique sont vraies.

Caractérisation de la classe de complexité VP
Natacha Portier

La classe de complexité VP a été définie par Valliant. C'est la classe des polynômes calculables par des circuits de taille polynomiale. L'année dernière Guilaume Malod est venu nous présenter sa thèse "polynômes et coefficients", dans laquelle il donne une caractérisation de la classe VP. Malheureusement un des lemmes sur lesquels elle repose était souffrant et on se demandait si on allait pouvoir guérir le malade. Je vais vous présenter le vaccin. Bien sur, je représenterai également l'ensemble du contexte, pour que personne ne souffre de ne pas avoir vu l'exposé de Guillaume, ou bien de l'avoir oublié.

Dynamiques expansives dans les automates cellulaires
Guillaume Theyssier

L'expansivité est une propriété naturelle des systèmes dynamiques sur laquelle repose une définition du chaos souvent rencontrée dans la littérature. Dans le cas particulier des automates cellulaires, cette propriété devient très contrainte. Nous montrerons qu'elle ne peut apparaître qu'en dimension 1, qu'elle impose à la fonction globale l'automate de fortes conditions de régularités et qu'elle induit naturellement un système dynamique conjugué très simple. En outre, nous présenterons et discuterons deux problèmes ouverts : celui de la décdabilité de cette propriété et celui de la conservation de l'expansivité par facteurs.

Langages de signaux reconnus par des automates finis
Jérôme Durand-Lose

Cet exposé présente des recherches en cours. (Attention, les signaux ne sont pas du tout ceux de mon HDR.)

Dans une tentative de construire une théorie des langages dans un contexte où apparaît le continu, nous nous intéressons à la manipulation de fonctions sur un intervalle de R au travers d'automates finis. Nous nommons pré-signal toute fonction de [0,1[ dans un alphabet fini. Nous définissons un critère d'acceptation par automate fini (pour signaux, AFS) par le biais de mots approximant un pré-signal. Un signal est alors un classe d'équivalence pour la non-distinction par AFS (i.e. deux pré-signaux sont équivalents si tout AFS acceptant l'un accepte l'autre).

Sur un exemple, nous montrons qu'un AFS peut caractériser un signal composé de mots fractals isomorphes. Nous prouvons que l'ensemble des signaux à la même cardinalité que R; et donc que presqu'aucun signal n'est caractérisé par un AFS. En fonction du temps restant, nous pourrons parler de concaténation (entre signaux ou langages acceptés) et d'opérations booléenne sur les langages acceptés par ASF où beaucoup de questions sont ouvertes.

Dynamique lente dans une chaîne de Markov Metropolis sur le descent model
V. Desoutter

Les verres structuraux, verres de spin ou matériaux granulaires sont des systèmes physiques présentant des temps de relaxation vers l'équilibre extrêmement grand devant les temps d'expériences en laboratoire. Ils sont ainsi considérés comme perpétuellement hors d'équilibre. Les méthodes de physique statistique à l'équilibre ne peuvent plus s'appliquer, ce qui rend leurs compréhensions plus délicates. Je présenterai ici un nouveau modèle unidimensionnel, simple, sans désordre, présentant une dynamique lente et du vieillissement dans la limite de température nulle. Cette dynamique lente est due uniquement à des barrières entropiques. On peut résoudre de façon exacte la statique du modèle. Nous avons dérivé une équation d'évolution pour les modes lents de la dynamique qui sont responsables du vieillissement. Cette équation est équivalente à un marcheur aléatoire Markovien sur les niveaux d'énergie. La dynamique de ce dernier modèle peut être résolu analytiquement en dépit de quelques approximations basiques. On montre qu'il présente bien du vieillissement ainsi qu'une lente relaxation de son énergie moyenne en : 1/ln(t).

Une nouvelle caractérisation des classes de complexité algébrique VP et VQP
G. Malod

Nous présentons la théorie de Valiant, qui définit un analogue algébrique de la classe P, la classe des suites de polynômes VP, considérées comme facilement calculables, parmi les suites de polynômes facilement descriptibles de la classe VNP. Nous donnons une caractérisation de la classe VP par les circuits multiplicativement disjoints et en déduisons un preuve simplifiée de l'égalité des classes VNP et VNPe. Nous poussons cette étude plus loin en introduisant les circuits fortement multiplicativement disjoints et nous montrons qu'ils permettent de décrire la classe VQP des suites de polynômes de complexité quasi-polynomialement bornée. Nous montrons ainsi simplement la VQP-complétude du déterminant et d'autres suites de polynômes, en répondant à une conjecture de Peter Bürgisser.

Quelques algorithmes appliqués à la biologie
N. Portier

J'ai assisté il y a quelques semaines à la dernière journée d'un colloque Algo-Bio. Trois exposés m'ont particulièrement intéressée. Je vous en présente les grandes lignes :

1. Algorithms for phylogenetic footprinting (Mathieu Blanchette - Université de Washington)

   Il s'agit de chercher dans le génome des morceaux qui servent effectivement. Pour cela, on part de l'hypothèse qu'un mot qui veut dire quelquechose mute peu. On utilise les arbres phylogénétiques connus (et en passant on légitime en cela la construction de tels arbres, sujets de recherche actif, cf. pour ceux qui s'en rappellent un exposé d'un ancien MIM l'année dernière, Julien Ménier)

2. Sorting by reversals: an explicitly graphic presentation (Anne Bergeron - Université de Montréal)

   Il s'agit cette fois de calculer des distances entre espèces (pour construire par exemple ces fameux arbres phylobidules). Pour cela, on cherche quel enchainement minimal de transformations élémentaires mène de l'un à l'autre. On se ramène à un problème combinatoire, qui est une sorte de généralisation de la décomposition des permutations en produit de transposition, où on ajoute des signes.

3. On maximal instances for the syntenic distance (Guillaume Fertin - Université de Nantes)

   Encore une fois on veut calculer des distances entre génomes pour pouuvoir dessiner des arbres. On suppose que les deux génomes ont exactement les memes genes, mais regroupés différemment dans les chromosomes. Combien d'opérations de base (du type union de deux chromosomes) faut-il pour passer de l'un à l'autre ? La question est reliée au joli problème suivant : un secret est une chose qu'on ne dit qu'à une personne à la fois. Quand deux personnes se rencontrent, elles échangent tous leurs secrets. Imaginez un ensemble de n personnes ayant chacune leur secret. Quel est le nombre minimal de rencontres (à 2 personnes) pour que tout le monde sache tout ?

G. Radenne
Core de n-rubans et équilibrage

On s'interesse aux n-cores, objets géométriques qui apparaissent dans les pavages par rubans des diagrammes de Ferrers. La bijection de Stanton-White, outil fondamental pour l'étude de tels pavages, donne un codage pour ces n-cores, laissant apparaître une structure de groupe, mais elle n'a a priori rien de naturel. On verra qu'en fait ce codage peut se rattacher à la notion d'équilibrage pour un n-coloriage, qui explicite la structure de groupe. On étudiera plus en détail cette structure, en particulier les divers opérateurs agissant sur ce groupe, ainsi qu'une norme tiré du codage et liée à la taille du core correspondant.

Des colorations apériodiques induites par les rotations discrètes
B. Nouvel

Nous définirons une classe de colorations (applications de Z² dans un ensemble fini de couleurs Q) induites par des rotations discrètes. Les propriétés fondamentales de celles-ci seront rappelées. Les cas périodiques, apériodiques et asymétriques seront détaillés. Puis l'attention sera portée sur la question de l'emploi de celles-ci pour la génération de familles de tuiles de Wang ``purement'' apériodiques. Si le temps nous le permet nous montrerons comment faire des rotations discrètes à partir de ces colorations et nous discuterons alors aussi de l'intérêt d'étendre les algorithmes de Gosper.

« Lorentz Lattice Gas»  ou Fourmi 5
A. Gajardo

Le modèle du gaz de Lorentz dans la grille a été introduit en même temps que sa soeur la fourmi de Langton. Les deux ont été étudiés parallèlement avec des méthodes et des objectifs différents. Dans un sens général, il s'agit de systémes dynamiques consistant en un robot qui se déplace sur un espace discret en suivant une régle déterministe, une sorte de machine de Turing n-dimensionnelle. Dans cet exposé, on fera un bilan des résultats théoriques existants.

Existence et nombre maximum de points fixes en réseaux booléens
J. Aracena

Je commencerai par définir les reseaux booléens et expliquer leur importance pour la modélisation de réseaux de régulation génétiques. Ensuite, je montrerai quelques resultats sur l'existence et le nombre maximum de points fixes pour des reseaux booléens particuliers. Ces résultats sont fortement liés aux propriétés de l'architecture du graphe de connexion du réseau.

Le problème du sous-groupe caché en calcul quantique
V. Nesme

Après une présentation du modèle de calcul quantique, assortie de quelques exemples illustrant sa différence avec le calcul classique, on introduira le problème du sous-groupe caché, motivé entre autres par le fait que le problème de l'isomorphisme de graphes s'y réduit ; puis l'on présentera les méthodes usuelles pour le résoudre (à base d'échantillonnage de Fourier) et les classes de groupes auxquelles ces méthodes s'appliquent.

Autour de la largeur de branche et de la largeur arborescente des graphes planaires
F. Mazoit

Je commencerai par définir les deux paramètres que sont la treewidth et le branchwidth. Je montrerai comment ces paramètres dérivent d'une même structure et sont donc fortement reliés. Ensuite, je présenterai les aspects plus particuliers des graphes planaires et entre autre, comment on peut associer a chacun de ces paramètres un jeu formel pour lesquels on construit une stategie gagnante pour l'un des joueurs.

Orientations of weak triangulations
M. Matamala

A weak-triangulation is a bridgeless connected plane graph G such that every inner face of G is bounded by a cycle of length three. We denote by WT the class of all weak-triangulations and by C_∞(G) the boundary of the outerface of a graph G ∈ WT. An orientation H of a graph G ∈ WT is good if every arc in H lays in a directed cycle of length three. A k-wheel, denoted by W_k, is a 2-connected weak-triangulation on k+1 vertices, with C_\infty(Wk) being a cycle of length k. We denote by OWC the subfamily of WT defined recursively as follows:

• For all k ≥ 1, W_2k+1 is in OWC.
• Let G ∈ WT be with induced subgraphs G₁ and G₂ in WT such that G=G₁ ∪ G₂, G₁ ∩ G₂={e} and e is an edge in C__{∞(Gi )} for i=1,2. If G₁,G₂ ∈ OWC then G ∈ OWC.

• If G is 2-connected then G has a good orientation if and only if G ∉ OWC.
• There exists an orientation H of G such that for all u,v ∈ V(G) : max {d_H(u,v), d_H(v,u)} ≤ 2d_G(u,v)+1.

Dynamic of cyclic automata over Z²
E. Moreno

A Cyclic Automata Network is a graph where each vertex has a state from a set with a cyclic order. The dynamic either keeps the state at a vertex or replace it by its next state if this appear in its neighborhood. In this work we study this dynamic over the 2-dimensional lattice and we construct a family of configurations having a periodicity superpolinomial in the number of initial non-quiescent states.

transparents.

Suites récurrentes linéaires - le point de vue informatique
E. Jeandel

L'importance des suites récurrentes linéaires n'est aujourd'hui plus à démontrer, tant elles interviennent naturellement dans nombre de problèmes, soient-ils informatiques, mathématiques, voire même, fait surprenant, physiques ou biologiques (sacré Fibonacci).

Nous aborderons ici la situation du point de vue informatique, c'est à dire en cherchant principalement à résoudre des problèmes naturels : est-ce qu'une suite récurrente linéaire s'annule, est-ce qu'elle s'annule une infinité de fois.. Nous nous intéresserons donc à des questions de complexité (indécidabilité de problèmes analogues, problèmes NP-durs sous-jacents), et donnerons quelques indications sur des variantes faciles (décidabilité pour les suites de degrés faibles, et lien avec les problèmes d'atteignabilité point-espace vectoriel).

transparents.

Théorème PCP et applications
F. Magniez

Dans les années 90, un théorème frappant a été prouvé : il existe une manière d'écrire des preuves et une méthode probabiliste pour vérifier leur validité, telles qu'un vérifieur n'a besoin de lire que 3 bits de la preuve pour se convaincre avec grande probabilité que la preuve est correcte. Compris dans le contexte de la classe NP, ce théorème fournit une alternative au théorème de Cook. Pour la première fois, il fournit une caractérisation probabiliste de la classe NP. Cette caractérisation fournit un des outils actuels les plus puissants pour prouver des résultats d'inapproximabilité de problèmes d'optimisation Max-SNP difficiles tels que Max-k-Function-Sat, Max-k-Sat, Max-Cut, Max-Clique, ...

Au cours de cette journée (un exposé le matin et un l'après-midi), nous présenterons le théorème principal PCP(log n,1)=NP, et montrerons quelques une de ses applications. La preuve du théorème sera l'occasion d'introduire plusieurs outils d'auto-test de propriétés algébriques.

Lectures conseillées : voir ici (en particulier les notes de cours de M. Sudan).

Groupe de travail exceptionnel
H. Benazza

Codes algébriques de Goppa.

Groupe de travail exceptionnel
Y. Gurevich + J. Kari

Deux exposés composeront cette séance :

• à 14h, Y.~Gurevich nous parlera d'Abstract State Machine ;
• à 15h environ, J.~Kari nous parlera de Snake Problems.

Pourquoi Gödel est-il un informaticien ?
Grégory Lafitte

Tout est dans le titre.

Automates temporisés (2/2)
J. Durand-Lose

Après un très bref rappel du modèle d'automate temporisés d'Alur et Dills, nous montrerons les résultats de complexité suivants :

• savoir si le langage (temporisé) reconnu est vide est PSPACE-complet ;
• savoir si un automate accepte tous les mots temporisés est indécidable.

transparents.

Groupe de travail extraordinaire
M. Nivat

Autour des suites homogènes 2D, des permutations cordales et des pavages du plan...

Problèmes de sandwich dans les graphes et ordres partiels
E. Lebhar

La notion de graphe sandwich a été introduite en 1995 par Golumbic : il s'agit d'un graphe compris entre un graphe G et un des sous-graphes de G. L'étude de problèmes d'analyse de séquence d'ADN ou encore de synchronisation de processeurs peut se traduire en une recherche d'un graphe sandwich vérifiant une propriété particulière. Nous nous sommes intéressés aux modules sandwich, le problème est de trouver un graphe sandwich contenant un module, en cherchant à les énumérer nous corrigeons un théorème faux publié à ce sujet. Puis nous avons cherché à adapter la notion aux graphes orientés, et donc aux ordres, en découvrant d'intéressants problèmes, comme celui de l'ordre sandwich de permutation.

transparents.

Automates temporisés (1/2)
J. Durand-Lose

Introduction à la chose par quelqu'un qui a juste potassé un peu. Toutes les questions sont les bienvenues. La première partie de l'exposé est disponible ici.

Graphes d'automates pas tout à fait finis...
C. Papazian

... ou comment la complexité locale se traduit en complexité globale.

Matrices de Vandermonde, NP-complétude, et sous-espaces supplémentaires.
P. Koiran

Nous construisons en temps polynomial des familles de sous-espaces de dimension r de Cⁿ avec la propriété suivante : tout sous-espace de dimension n-r de Cⁿ est supplémentaire à au moins l'un des membres de la famille. Nous donnons également une nouvelle preuve de NP-complétude pour le problème suivant : étant donnés deux entiers n et m avec m au moins égal à n, et une matrice A de taille nxm à coefficients entiers, décider s'il existe un sous-déterminant nxn de A qui est égal à 0. Dans les deux cas il s'agit essentiellement de résultats de dérandomisation.

PRIMES in P
B. Poizat

Le 4 août dernier, Manindra Agrawal et deux de ses élèves ont annoncé qu'ils avaient un algorithme en temps polynomial pour tester si un nombre est premier. Leur article est disponible sur www.cse.iitk.ac.in.

Comme depuis l'année passée le LIP et l'IGD sont partenaires d'une activité de coopération avec Agrawal et Biswas, de l'Indian Institute of Technology à Kanpur, nous ne pouvons moins faire que de consacrer la première séance de notre séminaire de complexité de cette année à cet article !

L'article est clairement écrit, mais, comme je ne suis pas théoricien des nombres, je ne suis pas certain de pouvoir bien en rendre compte dans tous ses détails, et j'invite ceux qui viendront à mon exposé à y jeter un coup d'œil auparavant.