MC2 : Modèles de calcul, Complexité, Combinatoire

Groupe de Travail

Le groupe de travail a lieu habituellement le mercredi matin à 10h15.

 

Cliquez ici pour la nouvelle page du groupe de travail 2015-2016

Groupes de travail 2014-2015 (Organisateur : Julien Bensmail)

 

Prochain(s) groupe(s) de travail

9 juillet 2015 Matthieu Rosenfeld (ENS Lyon) : Deciding if a morphic word is abelian power-free 

Two words are abelian-equivalent if they are permutations of each other and an abelian-$k$-power is the concatenation of $k$ consecutive words that are abelian equivalent. Erdös asked in two different occasions if there are:
-an infinite word over the binary alphabet that avoids large powers,
-an infinite word over 4 letters that avoids abelian 2-powers.
Both questions have been answered positively since, but this leads to the following questions:
-Is there an infinite word avoiding large abelian-2-powers over 3 letters?
-Is there an infinite word avoiding large abelian-3-powers over 2 letters?

In order to answer these questions we find an algorithm to decide if the iterations of a morphism give a word without abelian-$k$-powers and then apply it to some morphisms. Using the same idea we can also answer some other questions concerning the avoidability of additive-powers or p-abelian-powers.  

Précédent(s) groupe(s) de travail

1 juillet 2015 Anna Frid (Univ. Aix-Marseille) : Sur la complexité des permutations infinies ergodiques

(travail en commun avec S. Avgustinovich et S. Puzynina) 

Une permutation infinie est un ordre sur N. Nous pouvons considérer une permutation comme une structure analogue à un mot, et en particulier, étudier son ensemble de facteurs. Comme nous avons montré avec D. Fon-Der-Flaass en 2007, la complexité d'une permutation non périodique peut être majorée par toute fonction croissante non bornée. Cependant, cela n'est plus le cas si on ne considère que les permutations "ergodiques". Une permutation est "ergodique" si elle correspond à une suite de nombres réels deux à deux distincts entre 0 et 1 telle que la probabilité qu'un nombre soit inférieur à p est p pour tout p.

Nous montrons que la complexité minimale d'une permutation ergodique est n, et que les permutations dont la complexité est n sont exactement les permutations sturmiennes. 

 

24 juin 2015 Markus Whiteland (Univ. Turku, Finland) : A Square Root Map on Optimal Squareful Words

(joint work with J. Peltomaki)

Let x be an infinite word of the form $x = X_1^2 X_2^2 X_3^2 ...$ , where each $X_i^2$ is a minimal square, that is, a square with no proper square prefix. Define the square root of $x$ as $\sqrt{x} = X_1 X_2 X_3 ...$ . We study relations between $x$ and $\sqrt{x}$ when $x$ is optimal squareful. An infinite word is squareful if there exist $N \in \mathbb{N}$ and a set of minimal squares, such that each factor of length $N$ begins with one of the squares. A squareful word is optimal, if it is aperiodic and the set of minimal squares has least possible size. A result of Kalle Saari (2010) characterizes precisely the set of optimal squareful words and shows that every Sturmian word, i.e., a coding of an irrational rotation associated with an irrational slode $\alpha$ and an intercept $\rho$, is optimal squareful.

We show a surprising fact that given a Sturmian word $s$, we have $\sqrt{\Omega_s} \subset \Omega_s$, where $\Omega_s$ is the shift orbit closure of $s$. More precisely, we show that the words $s$ and $\sqrt{s}$ have the same slope and that the intersept of $\sqrt{s}$ can be computed from the intersept of $s$. Related to this, we study "Sturmian solutions" to the equation $(X_1 ... X_k)^2 = X_1^2 ... X_k^2$, where each $X_i^2$ is a minimal square.

Concerning general optimal squareful words, the relations between $x$ and $\sqrt{x}$ can have quite differing behaviours. For example, there exist optimal squareful words $x$ such that $\sqrt{\Omega_x} \cap \Omega_x = \emptyset$. On the other hand, there exist both Sturmian and non-Sturmian optimal squareful fixed points of the square root map. Also, most surprisingly, there exist (aperiodic) optimal squareful words $x$ such that $\sqrt{x}$ is periodic.  

 

8 avril 2015 Bruno Grenet (LIRMM, Université de Montpellier) : Calcul des racines de polynômes à coefficients dans un corps fini de caractéristique friable

Trouver les racines d'un polynôme à coefficients dans un corps fini est un problème fondamental du calcul formel, qui sert de brique de base à de nombreux algorithmes du domaine (factorisation, interpolation, ...). D'autre part, il s'agit de l'un des rares problèmes que l'on sait résoudre en temps polynomial probabiliste mais pas en temps polynomial déterministe.
Nous avons récemment proposé une nouvelle approche pour ce problème, basée sur un outil issu de l'analyse numérique et appelé transformée de Graeffe. Cette approche nous a permis de donner plusieurs algorithmes, déterministe, probabiliste et heuristique. Ces algorithmes sont particulièrement adaptés aux corps finis de caractéristique friable : pour ceux-ci, nous obtenons la meilleure complexité déterministe connue et l'implantation de nos algorithmes dans le logiciel libre Mathemagix est sensiblement plus rapide que les logiciels existants.

Travail réalisé en commun avec Grégoire Lecerf et Joris van der Hoeven.  

 

11 mars 2015 Benjamin Hellouin (Andrés Bello University, Chile) : Limit measures in cellular automata

We consider the time evolution of cellular automata when strating from an initial configuration sampled at random, which corresponds to study their action on probability measures. I will present an overview on my work on limit measures of these systems, which can be seen as theit typical asymptotic behavious or their output as a probabilitic algorithm.

In dimension 1, the measures that can be reachedstarting from a simple measure, e.g. the uniform measure, can be described by computability conditions. Work is ongoing for higher dimensions, and we have some partial results. However, this approach cannot handle limit measures with full support, that can be reached only by surjective dynamics.

Although surjective cellular automata possess computational power, their action on probability measures is very rigid and little is known about it. We conjecture that some subclasses make all simple initial measures converge to the uniform measures, and this is backed up by experimental evidence. We produced the first complete proof of this phenomenon in a cellular automaton with specific algebraic properties, using self-similar structures in its time evolution. 

 

7 janvier 2015 Nicolas de Rugy (U. Paris-Diderot) : Model checking en logique de dépendance 

La logique de dépendance et ses variantes (indépendance et inclusion) ont été introduites par Vänäänen il y a quelques années pour parler de façon "propre" de dépendance en logique. Je présenterai cette logique et ses résultats principaux en complexité. 

 

17 décembre 2014 Luis Pedro Montejano (U. Montpellier 2) : Transversal to the convex hulls of all k-sets of discrete subsets of Rd

Let k,d,lambda >= 1 be integers with d >= lambda. What is the maximum positive integer n such that every set of n points in Rd has the property that the convex hulls of all k-sets have a (special) transversal d-lambda-plane? What is the minimum positive integer n such that every set of n points in Rd has the property that the convex hulls of all k-sets do not have a (special) transversal d-lambda-plane? We investigate these two questions for transversal d-lambda-planes and special transversal d-lambda-planes. A Special transversal (d-lambda)-plane for a set of points S in Rd is an affine subspace of dimension d-lambda that goes through d-lambda+1 points of S. First question is related with Kneser hypergraph and its chromatic number (when lambda=1, it is equivalent to Kneser’s conjecture). We will see how answering first question could give improvements to this problem.  

 

3 décembre 2014 Svetlana Puzynina (ENS Lyon) : Infinite self-shuffling words

In this talk we introduce and study a new property of infinite words: An infinite word x on an alphabet A is said to be it self-shuffling, if x admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$ with $U_i,V_i \in A^*$. In other words, there exists a shuffle of x with itself which reproduces x. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic uniformly recurrent word contains a non self-shuffling word in its shift orbit closure. On the other hand, we build an infinite word such that no word in its shift orbit closure is self-shuffling.

We prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words (except those of the form aC where a ∈ {0,1} and C is a characteristic Sturmian word). We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. One important feature of self-shuffling words is its morphic invariance: The morphic image of a self-shuffling word is again self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion has other unexpected applications: For instance, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist.   

 

22 octobre 2014 Irena Penev (ENS Lyon) : Amalgams and chi-boundedness

A class of graphs is hereditary if it is closed under isomorphism and induces subgraphs. A hereditary class GG is chi-bounded if there exists a function f such that every graph G in GG satisfies chi(G) <= f(omega(G)), where chi(G) is the chromatic number of G, and omega(G) is the clique number (i.e. the maximum size of a clique) of G. For many hereditary classes of graphs, there is a decomposition theorem of the following form: every graph in the class either belongs to some class of well-understood basic graphs, or it admits one of several decompositions. This raises the following question: which graph decompositions preserve chi-boundedness?

Formally, we say that a graph decomposition D preserves chi-boundedness if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits the decomposition D, we have that GG* is chi-bounded. This can be generalized to several decompositions: we say that graph decompositions D1,...,Dk together preserve chi-boundedness if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits one of D1,...,Dk, we have that GG* is chi-bounded. The fact that each of D1,...,Dk individually preserves chi-boundedness does not imply that D1,...,Dk together preserve it. In this talk, we present the proof of the following result: proper homogeneous sets, clique-cutsets, and amalgams together preserve chi-boundedness. As an application of this result, as well as of a decomposition theorem for cap-free graphs (due to Conforti, Cornuejols, Kapoor, and Vuskovic), we show that the class of graphs that do not contain any subdivision of the complement of the four-edge path as an induced subgraph is chi-bounded.   

 

15 octobre 2014 Ignacio Garcia Marco (ENS Lyon) : On the Möbius function of semigroup posets

Fifty years ago, Rota introduced the Möbius function of a (locally finite) poset as a tool to solve a wide range of enumeration problems. This notion turns out to be a generalization of the classical arithmetic Möbius function, which corresponds to the poset of positive integers partially ordered by divisibility.
For every (finitely generated) subsemigroup S of N^m, we consider the poset Z^m partially ordered by: x <= y if and only if y – x belongs to S. The objective of this talk is to present some results relating the Möbius function of this poset with the Hilbert series of the semigroup S. These results allow us to describe explicitly the Möbius function for several families of semigroups.

The results are included in arXiv:1404.5710, a joint work with Jonathan Chappelon, Luis Pedro Montejano and Jorge Luis Ramírez Alfonsín.  

 

8 octobre 2014 Nathalie Aubrun (ENS Lyon) : Effective Subshifts vs. Sofic subshifts in the hyperbolic plane

Multidimensional subshifts of finite type (SFT) and sofic subshifts are closed and shift-invariant subsets of colourings of Z^d for d >= 2 given by local rules (in these cases a finite set of forbidden patterns, plus a letter-to-letter map for sofic subshifts), and enjoy strong computational properties. For instance, it is not possible to decide whether such a subshift is empty or not. A clever result by Hochman (2007) states that with an increase by 1 of the dimension, effective subshifts (given by a recursively enumerable set of forbidden patterns) are very close to sofic subshifts. Sets of colourings (given by forbidden patterns) can be defined on structures more general than Z^d, for instance finitely presented groups, and a natural question is to determine whether results similar to Hochman's can be proved in this case. In this talk I will explain the recent progress made in order to prove the following conjecture: effective sets of colourings are sofic in the hyperbolic plane.

This is joint work with Mathieu Sablik.  

 

1 octobre 2014 Volkher Scholz (ETH Zürich) : Quantum-proof extractors, operator spaces and SDP’s

Randomness extractors are an important building block for classical and quantum cryptography as well as for device independent randomness amplification and expansion. It is known that some constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC’07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent objects are quantum-proof: we first rephrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. Using semidefinite programming (SDP) relaxations of this completely bounded norm, we recover all known classes of quantum-proof extractors as well as derive new ones.

Based on arXiv:1409.3563 and joint work with Omar Fawzi and Mario Berta. 

 

17 septembre 2014  Pascal Koiran (ENS Lyon) : A tau-conjecture for Newton polygons

One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial X^i Y^j appears in P with a nonzero coefficient. We conjecture that when P is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this "tau-conjecture for Newton polygons,'' even in a weak form, implies that the permanent polynomial is not computable by polynomial size arithmetic circuits. We make the same observation for a weak version of an earlier "real tau-conjecture.'' Finally, we make some progress toward the tau-conjecture for Newton polygons using recent results rom combinatorial geometry.

Joint work with Natacha Portier, Sébastien Tavenas and Stéphan Thomassé.   

 

2 octobre  Nicolas Bousquet (LIRMM, Montpellier, France) : Recolorer les graphes de treewidth bornée

Résumé: (travail réalisé avec Marthe Bonamy)
Soit G un graphe et k un entier. On se pose la question suivante: étant données deux k-colorations (propres) de G, peut-on recolorer le graphe G de l'une à l'autre :
- En recolorant un sommet à la fois,
- Et de façon à ce que G soit coloré proprement à chaque étape.
Dans une première partie, on survolera les résultats connus en recoloration de graphes (chemins, arbres, graphes triangulés). Nous montrerons ensuite que les graphes de largeur arborescente t peuvent être recolorés dès que k vaut au moins l+2, et ce en un nombre quadratique d'étapes. La borne sur le nombre de recolorations est optimale à un facteur constant multiplicatif près. On parlera ensuite du cas des co-graphes et des graphes distance héréditaire.

30 octobre  Julien Cassaigne (Institut de mathématiques de Luminy, Marseille, France) : Éviter les cubes additifs

Résumé: Pirillo et Varricchio ont posé en 1994 la question suivante : existe-t-il une suite d'entiers bornée telle que deux blocs consécutifs de même longueur n'aient jamais la même somme ?
Ce problème fait partie des problèmes d'évitabilité de motifs dans les mots infinis, le motif à éviter étant ici appelé carré additif. Il est encore ouvert à ce jour.

Nous considérons dans cet exposé le cas des cubes additifs, c'est à dire du motif formé non pas de deux mais de trois blocs consécutifs de même longueur et de même somme. Nous montrons au moyen d'une construction explicite qu'il est évitable sur un alphabet à 4 éléments. Nous nous demandons ensuite dans quelle mesure une construction similaire serait possible pour les carrés additifs (dans l'hypothèse où la réponse à la question de Pirillo et Varricchio serait positive).

6 novembre  Virginie Lerays (Paris VII, France) : Lower bounds on information complexity via zero-communication protocols and applications

Information complexity is a powerful tool to study communication complexity. It is even conjectured that these quantities are equivalent. We show that almost all known lower bound methods for communication complexity are also lower bounds for information complexity. To do that, we define a relaxed version of the partition bound of Jain and Klauck, which subsumes all rectangle and norm-based techniques, and we show that it lower bounds the information complexity.

Our result uses a connection between rectangle techniques and zero-communication protocols where players can abort (Laplante, Lerays, Roland 2012). More precisely, the maximum achievable probability that the protocol doesn't abort, which is called efficiency, gives a lower bound on communication complexity which corresponds to the relaxed partition bound. We use compression techniques to relate IC to efficiency.

In this talk, I will first make the link between zero communication protocols, communication complexity and rectangle techniques and then present the compression technique which is similar to those of Braverman and Weinstein 2012 and Braverman 2012. I will also present some applications of our theorem.

12 novembre  Irène Marcovici (Paris VII, France) : Automates cellulaires probabilistes et mesures spécifiques sur des espaces symboliques

Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Les ACP sont utilisés en informatique comme modèle de calcul, ainsi qu'en biologie et en physique. Ils interviennent aussi dans différents contextes en probabilités et en combinatoire.
Un ACP est ergodique s’il a une unique mesure invariante qui est attractive. Dans le cas des AC déterministes, nous prouvons que l’ergodicité est équivalente à la nilpotence, ce qui fournit une nouvelle preuve de l'indécidabilité de l'ergodicité pour les ACP. Alors que la mesure invariante d’un AC ergodique est triviale, la mesure invariante d’un ACP ergodique peut être très complexe. Nous proposons un algorithme permettant d’échantillonner parfaitement cette mesure.
Nous nous intéressons à des familles spécifiques d’ACP, ayant des mesures de Bernoulli ou des mesures markoviennes invariantes, et étudions les propriétés de leur diagrammes espace-temps.
Nous résolvons le problème de classification de la densité sur les grilles de dimension supérieure ou égale à 2 et sur les arbres.
Enfin, nous nous intéressons à d'autres types de problèmes. Nous donnons une caractérisation combinatoire des mesures limites pour des marches aléatoires sur des produits libres de groupes. Nous étudions les mesures d'entropie maximale de sous-décalages de type fini sur les réseaux et sur les arbres. Les ACP réapparaissent dans ce dernier travail.

27 novembre  Jarkko Kari (University of Turku, Finland) : Universal Pattern Generation by Cellular Automata

A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply by constants 3 and 3/2 in base 6. We discuss the connections of these automata to some difficult open questions in number theory, and we pose several further questions concerning pattern generation in cellular automata.

4 décembre  Guillaume Malod (Paris 7, France) : Bornes inférieures pour les formules de profondeur 4 calculant le produit itéré de matrices

(travail commun avec Hervé Fournier, Nutan Limaye et Srikanth Srinivasan) Nous étudions la complexité arithmétique du produit itéré de matrices, un calcul fondamental de complexité équivalente au déterminant. Nous montrons que toute formule mutlilinéaire homogène de profondeur 4 calculant le produit de d matrices de taille n x n a une taille n^Ω(√d) (quand d = n^O(1)). Nous étudions aussi les formules où l'arité entrante des portes de multiplication satisfait certaines bornes et la borne inférieure que nous obtenons montre le caractère optimal de la construciton de Tavenas (MFCS, 2013).

8 janvier  Nicolas de Rugy-Altherre (Paris 7, France) : Complexité du fermionant et de l'immanant

Le fermionant est un polynôme introduit récemment par des physiciens. L'immanant a été introduit par Littlewood dans les années 40. Il se trouve que l'un et l'autre sont des généralisations intéressantes du permanent et du déterminant.

Nous classifions la complexité de leurs représentation par des circuits arithmétiques. Nous étendons de plus cette classification à la complexité du fermionant vu comment fonction de comptage.

Ces travaux se justifient d'une part par l’intérêt intrinsèque du fermionant et encore plus de l'immanant ; et d'autre part par la lumière que cela jette sur les classes de complexités algébriques, VP et VNP.

15 janvier Irena Penev  (ENS Lyon, France) : A Composition Theorem for {P5,P5c}-Free Graphs

If HH is a family of graphs, a graph G is said to be HH-free provided that G does not contain (an isomorphic copy of) any graph in HH as an induced subgraph. P5 is a four-edge path, and P5c is its complement. In this talk, I will present some new results on the structure of {P5,P5c}-free graphs.

A graph G is said to be prime if it cannot be obtained by substitution from smaller graphs (equivalently: if it does not contain a proper homogeneous set). Fouquet proved that every prime {P5,P5c}-free graph is either a cycle of length five (denoted by C5), or a {P5,P5c,C5}-free graph. Since P5, P5c, and C5 are all prime graphs, Fouquet's theorem reduces the problem of describing the structure of {P5,P5c}-free graphs to the problem of describing the structure of {P5,P5c,C5}-free graphs.

In this talk, I will first present a decomposition theorem for {P5,P5c,C5}-free graphs, which states that if G is a prime {P5,P5c,C5}-free graph, then either G is a split graph (i.e. a graph whose vertex-set can be partitioned into a clique and a stable set), or G or its complement admits a "split graph divide," a new kind of decomposition, which I will describe in the talk. I will then explain how this new decompositon can be turned into an operation, called "split graph unification," which preserves the property of being H-free for each graph H in {P5,P5c,C5}. This yields a composition theorem for {P5,P5c,C5}-free graphs, which states that a graph G is {P5,P5c,C5}-free if and only if it can be obtained from split graphs by repeatedly applying substitution, complementation, and split graph unification. Together with Fouquet's result, this implies a composition theorem for {P5,P5c}-free graphs, which states that a graph G is {P5,P5c}-free if and only if it can be obtained from split graphs and cycles of length five by repeatedly applying substitution, complementation, and split graph unification.

Even though all operations used in our composition theorem for {P5,P5c}-free graphs are class-preserving, this theorem is not quite a structure theorem for reasons that I will discuss in the talk. Thus, more work is needed in order to fully understand the structure of {P5,P5c}-free graphs, but this new composition theorem might well represent a good starting point.

This is joint work with Maria Chudnovsky and Peter Maceli.

27 janvier Svetlana Puzynina (Sobolev Institute of Mathematics): Additive combinatorics generated by uniformly recurrent words

A subset A of the set N of natural numbers is called an IP-set if A contains all finite sums of distinct terms of some infinite sequence of natural numbers. We show how certain families of aperiodic words of low factor complexity may be used to generate a wide assortment of IP-sets having additional nice properties inherited from the rich combinatorial structure of the underlying word. We consider Sturmian words and their extensions to larger alphabets (so-called Arnoux-Rauzy words), as well as words generated by substitution rules. Our methods simultaneously exploit the general theory of combinatorics on words, the arithmetic properties of abstract numeration systems defined by substitution rules, notions from topological dynamics including proximality and equicontinuity, and the beautiful and elegant theory, developed by N. Hindman, D. Strauss and others, linking IP-sets to the algebraic/topological properties of the Stone-Cech compactification of N. Using the key notion of p-lim_n, regarded as a mapping from words to words, we apply ideas from combinatorics on words in the framework of ultrafilters. Most of our results on IP-sets extend to central sets, which constitute a special class of IP-sets possessing rich combinatorial properties.
Together with the property of being IP-set, we consider two related additive properties of subsets of positive integers: We say that a subset A of N is finite (resp., infinite) FS-big if for each positive integer k the set A contains finite sums with at most k summands of some k-term (resp., infinite) sequence of natural numbers. By a celebrated result of Hindman (1974), the collection of all IP-sets is partition regular, i.e., if A is an IP-set, then for any finite partition of A, one cell of the partition is an IP-set. We prove that the collection of all finite FS-big sets is also partition regular. Using the Thue-Morse word we show that the collection of all infinite FS-big sets is not partition regular. The talk is based on joint work with M. Bucci, N. Hindman, L. Q. Zamboni.

References
M. Bucci, S. Puzynina, L. Q. Zamboni, To appear in Ergodic Theory and Dynamical Systems. doi:10.1017/etds.2013.69
M. Bucci, N. Hindman, S. Puzynina, L. Q. Zamboni Additive properties of sets defined by the Thue-Morse word. Journal of Combinatorial Theory, Series A, 120 (2013), 1235--1245.
N. Hindman and D. Strauss, Algebra in the Stone-Cech compactification: theory and applications, 2nd edition, Walter de Gruyter & Co., Berlin, 2012.
S. Puzynina and L.Q. Zamboni, Additive properties of sets and substitutive dynamics. To appear in a forthcoming book ``Recent Mathematical Developments in Aperiodic Order" edited by J. Kellendonk, D. Lenz and J. Savinien.

5 février Timo Jolivet (LIAFA, Paris) : Propriétés indécidables d'ensembles fractals auto-affines et automates à plusieurs rubans

On s'intéresse à certaines propriétés topologiques des ensembles fractals du plan qui peuvent être définis par un système de fonctions itérées affines à coefficients rationnels. Pour cette classe, on prouve qu'être d'intérieur vide est indécidable. On considère aussi d'autres questions liées, comme la calculabilité de la dimension de Hausdorff. Les outils utilisés sont des problèmes de décision concernant les automates à plusieurs rubans. Travail réalisé en collaboration avec Jarkko Kari.

19 février Ignacio Garcia (I3M, Montpellier) : Complete intersection toric ideals of graphs

Let G be an undirected graph without multiple edges or loops, one can associate to G a toric ideal IG in a natural way. One may wonder if the algebraic properties of IG can be translated into combinatorial properties of G and vice versa. In this talk we focus on characterizing when IG is a complete intersection in combinatorial terms. More precisely, we provide both an algorithm that receives G as input and determines whether IG is a complete intersection, and a combinatorial description of the graphs G such that IG is a complete intersection.
All the results presented in this talk are part of [1], a joint work with Isabel Bermejo and Enrique Reyes.
References
[1] I. Bermejo, I. García-Marco and E. Reyes, Complete intersection graphs, arXiv:1210.1950.

26 février Pascal Vanier (LACL, Paris 12) : Degrés Turing des sous-shifts minimaux

Les sous-shifts sont des sous-ensembles de Z^d fermés invariants par translation, ou
de manière équivalente, définissables par une famille de motifs interdits. Un sous-shift
est minimal si il ne contient proprement aucun autre sous-shift, tous les sous-shifts
contiennent donc un sous-shift minimal. Un sous-shift minimal a la particularité que tous
ses éléments ont les mêmes motifs et que pour toute motif de taille n apparaîssant dans une
configuration, il existe un N tel que dans toute fenêtre de taille N de n'importe quelle
configuration ce motif apparaîsse. Nous nous intéressons ici à la structure calculatoire
de ces sous-shifts et en particulier à la structure de leurs ensembles de degrés Turing.

12 mars Omar Fawzi (Institute for Theoretical Physics, Zurich) : Achieving the limits of the noisy quantum-storage model

The goal of two-party cryptography is to enable Alice and Bob to solve tasks in cooperation even if they do not trust each other. Examples of such tasks include bit commitment, coin flipping and oblivious transfer. Unfortunately, it has been shown that even using quantum communication, none of these tasks can be implemented when the adversary is completely general.

As a result, assumptions on the power of the attacker need to be made. In complexity-theoretic cryptography, the computational power of the attacker is assumed to be limited, and security is based on a computational problem that is assumed to be hard. In this talk, we consider an information-theoretic limitation on the attacker: his storage device has a bounded capacity in storing quantum information. We give a protocol for two-party computation that is secure as soon as the adversary cannot store all the quantum bits communicated during the protocol. The honest players do not need any quantum storage to implement the protocol: only simple state preparation and measurements are required.

I will try to make the talk self-contained so that no knowledge of quantum information is necessary.

This is joint work with Frédéric Dupuis and Stephanie Wehner, available http://eprint.iacr.org/2013/360 and the full version http://arxiv.org/abs/1305.1316.

19 mars Marc Kaplan (DIRO, Montréal) : La dimension des systèmes physiques et leurs capacités de calcul

L'un des succès de l'information quantique vient de sa capacité à revisiter des concepts de physique en adoptant le point de vue de l'informatique. Nous nous proposons d'examiner cette question pour ce qui est de la dimension des systèmes physiques. Intuitivement, cette notion est liée au nombre de degré de liberté du système. Par exemple, dans le cas d'un système quantique, cette notion est capturée par la dimension de l'espace Hilbert qui le représente. Toutefois, une définition intrinsèque de la dimension devrait être indépendante de la représentation mathématique sous-jacente.

Dans notre travail, nous donnons deux définitions dans un cadre général qui généralise l'information classique et l'information quantique. La première notion, appelée dimension de mesure, est liée au nombre d'états distinguables du système. La seconde, appelée dimension d'information, au nombre d'états deux à deux distinguables. Ces deux notions sont proches, et même égales pour les systèmes classiques et quantiques. Toutefois, nous montrerons que l'écart de dimension n'est pas borné en général. Pour cela, nous exhibons une suite de systèmes physiques telle que l'écart de dimension augmente exponentiellement. Pour ces systèmes, cette amplification de l'écart implique également des performances accrues en terme de capacité de calcul.

Cette première approche suggère que pour des systèmes physiques raisonnables, la dimension de mesure et la dimension d'information doivent être égales. Toutefois, nous verrons qu'un tel axiome est insuffisant pour caractériser l'information quantique. Mais une connexion étonnante avec la capacité sans erreur des canaux bruités nous amènera à introduire une version asymptotique de la dimension. Enfin, nous introduirons quelques idées générales qui lient les notions de dimension avec la thermodynamique.

11 juin Bruno Grenet (LIX, Paris) : Calcul des facteurs de petit degré de polynômes lacunaires : une approche à la Newton-Puiseux

Dans mon exposé, je présenterai un nouvel algorithme polynomial pour le calcul des facteurs irréductibles de degré au plus d, avec multiplicité, de polynômes lacunaires à coefficients dans un corps de caractéristique 0. La représentation lacunaire d'un polynôme est la liste de ses monômes non nul, et la taille de cette représentation est en particulier logarithmique en le degré du polynôme. Certains facteurs peuvent alors être de taille exponentielle en la taille de l'entrée, d'où la restriction sur le degré des facteurs recherchés.
L'algorithme proposé est une réduction du problème au calcul des facteurs de degré borné de polynômes lacunaires à une variables d'une part, et de polynômes de petit degré d'autre part. Le cœur de la réduction utilise le polygone de Newton du polynôme d'entrée et sa correction est basée sur le développement en série de Puiseux des racines de polynômes à deux variables. En particulier, une borne est donnée sur la valuation d'une expression de la forme f(X, \phi) où f est un polynôme lacunaire et \phi une série de Puiseux annulant un polynôme de petit degré.

09 juillet Markus Bläser (Sarrebruck, Allemagne) : Fast matrix multiplication and related problems

In 1969, Strassen found a way to multiply 2 × 2-matrices with only 7 multiplications. This astonishing algorithm was the starting point of a fascinating development of faster and faster algorithms for matrix multiplication.
We give an overview of the history of fast algorithms for matrix multiplication and look at some other fundamental problems in linear algebra that are equivalent to matrix multiplication.

Slides de l'esposé.

Archives du groupe de travail

https://www.ens-lyon.fr/LIP/MC2/groupe-de-travail/ | Saved Saturday, February 24th, 2018 - 11:50 AM