MC2 Seminar
Welcome to the MC2 seminar webpage, here you can find all of the available information about future and past expositions.
Google calendar: Click here
Title: Lempel-Ziv : la catastrophe du premier bit.
Abstract: La robustesse du célèbre algorithme de compression de Lempel et Ziv n'est pas encore bien établie : en particulier, jusqu'à présent on ne savait pas si l'ajout d'un bit au début d'un mot compressible pouvait le rendre incompressible. C'est à cette question, popularisée par Jack Lutz sous le nom de « one-bit catastrophe » et dont on trouve trace dès 1998, que cet exposé va répondre. Nous montrerons qu'un mot « très compressible » reste compressible lorsqu'on ajoute un bit devant, mais que certains mots « peu compressibles » deviennent en effet incompressibles.
Title: White's conjecture and related matroid problems.
Abstract: When an ideal is defined only by combinatorial means, one expects to have a combinatorial description of its set of generators. An attempt to achieve this description often leads to surprisingly deep combinatorial questions. White's conjecture is an example. It asserts that the toric ideal associated to a matroid is generated by quadratic binomials corresponding to symmetric exchanges. In the combinatorial language it means that if two multisets of bases of a matroid have equal union (as a multiset), then one can pass between them by a sequence of symmetric exchanges between pairs of bases. White's conjecture resisted numerous attempts since its formulation in 1980. We will review the progress made in last years, which led to confirmation of the conjecture for high degrees (with respect to the rank of a matroid). We will also discuss its relations with other intriguing problems on matroids.
Title: Expansive Adics.
Abstract: Which dynamical systems defined by cutting and stacking (equivalently adic systems presented by ordered Bratteli diagrams) can be coded as subshifts? We say such a system is essentially expansive if there is a $k$ such that the partition by the levels of the towers at stage $k$ (equivalently the partition of the space of infinite paths determined by the first $k$ edges) generates the full sigma-algebra for every fully-supported finite ergodic invariant measure. In previous work with Sarah Bailey Frick and Sandi Shields, extending a result of Xavier Méla, we showed that every ordering of the Pascal graph produces an essentially expansive system. In joint work with Terry Adams and Sébastien Ferenczi, we show how to reorganize every odometer to produce essential expansiveness, completing the equivalence of the various concepts of rank one. Our sufficient condition for essential expansiveness applies to all cutting and stacking (or adic) systems and thus may be useful in other situations where a measure-theoretic isomorphism to a subshift would allow the application of ordinary symbolic methods to study dynamical properties.
Title: An introduction to periodic uniform computation : leader election on periodic cellular automata.
Abstract: Cellular automata are representative of massively parallel computational models. They consist in an infinite grid of cells that evolve synchronously at each time step. However, when it comes to adapt classical problems to cellular automata, their infinite nature can sometimes be seen as a hindrance, most notably because the definition and resolution of these problems only use a finite part of the cells. This talk will deal with some of the problems that arise when one tries to input a finite structure into an infinite uniform computational model, which has by definition no spatially distinguished point. In particular, we will consider two natural methods of input, which consist of bounding the finite input with special symbols, or using a periodic configuration whose period is the finite input. We will show how both those methods actually coincide on one-dimensional cellular automata, using two reciprocal reductions. The key point of the difficult reduction (simulating bounded input with periodic input) is a leader election algorithm that works on periodical configurations of cellular automata. This algorithm extensively uses the notion of signals on cellular automata to transform spatial differences into temporal differences. We will then dwell on possible extensions of the algorithm to higher dimension cellular automata and other parallel computational models (joint work with Gaétan Richard)
Title: Testing resiliency of instances using Integer Linear Programming
Abstract: We present a notion of resiliency for decision problems, which consists in deciding whether a given instance remains positive after any (appropriately defined) modification has been applied to it. In order to tackle these kinds of problems, we introduce a resiliency version of an Integer Linear Program (ILP), and present an algorithm for testing whether an ILP is resilient. As a direct application of our approach, we study a resiliency version of a generalization of the Set Cover problem, arising in the field of access control. We analyze its parameterized complexity by considering several parameterizations, establishing the frontier between tractable and intractable cases. This is joint work with Jason Crampton, Gregory Gutin and Martin Koutecky.
Title: Covering and tiling hypergraphs with tight cycles
Abstract: Given an hypergraph $F$, a perfect $F$-tiling in a hypergraph $H$ is a spanning collection of disjoint copies of $F$. A related notion is that of an $F$-covering, where we cover every vertex of the host graph $H$ with copies of $F$, but we no longer insist that the copies are disjoint. The problem of determining the least value of the minimum degree in a graph that ensures the existence of a perfect $F$-tiling (or $F$-covering) is well understood in the case of graphs. The situation is different for general uniform hypergraphs, where determining these thresholds is an active field of research. In this talk I will review some of the known results for hypergraphs and present some new results in the case where $F$ is a tight cycle; where tight cycles are a natural generalization of cycles for uniform hypergraphs. Joint work with Jie Han and Allan Lo.
Title: From partitions of infinite groups to a problem on sets of finite relational structures.
Abstract: Theorem: If a subgroup of the symmetric group of a countable infinite set is divisible then it is rank linear. The definition of rank linear for groups translates to a definition of rank linear for classes of sets of the form $Forb(\mathcal{B})$ via Fräissé theory. This and other notions involved in the partition theory of groups lead to very challenging problems for finite relational structures.
Title: Cycles de partage dans les plongements des graphes complets
Abstract: Dans un graphe plongé sur une surface, un cycle de partage est un cycle qui sépare le plongement en 2 parties connexes de genre strictement plus petit que la surface de départ. Par exemple, un cycle de partage d'un graphe plongé sur un double-tore séparera la surface en 2 tores troués. En général, il n'est pas évident qu'un plongement donné contient un cycle de partage. Il a été conjecturé par Barnette que si le plongement était une triangulation alors il devait contenir un tel cycle. Je donnerai des contre-exemples à une version forte de cette conjecture. Ces contre-exemples utilisent les plongements des graphes complets qui ont servi a démontrer la conjecture de Heawood. Je donnerai aussi des détails au sujet de ce résultat de 1970 qui permet de démontrer l'équivalent du théorème des 4 couleurs pour les surfaces autres que le plan.
Title: Dushnik-Miller dimension of TD-Delaunay complexes
Abstract: TD-Delaunay graphs, where TD stands for triangle-distance, are obtained from a variation of Delaunay triangulation consisting in replacing circles by homothetic triangles. It was noticed that every triangulation is the TD-Delaunay graph of a set of points in $\mathbb{R}^2$, and conversely. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by replacing equilateral triangles by regular simplexes in dimension $\mathbb{R}^d$. The abstract simplicial complexes obtained from a TD-Delaunay complex in dimension $d$ are of Dushnik-Miller dimension $d+1$. The converse holds for $d = $2 and $3$ and it was conjectured to hold for larger $d$. Our work with Daniel Gonçalves is to disprove the conjecture already for $d = 4$.
Title: $K4$-free graphs as a free algebra
Abstract:Graphs of treewidth at most two are the ones excluding the clique with four vertices ($K4$) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a free algebra. First we propose a syntax for denoting them: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they denote the same graph. Joint work with Enric Cosme-Llópez.
Title: Entropy of topologically mixing subshifts
Abstract: The entropy is a topological invariant of dynamical systems measuring their complexity. We study the infuence of topological mixing hypothesis on the entropy of effective one dimensional subshifts, and two dimensional subshifts of finite type. We would like to present some results about one di- mensional subshifts. The main result is that the entropies of O(n)-topologically mixing effective one dimensional subshifts are exactly the Π1-computable numbers. Under some low mixing condition, that is to say O(f(n))-mixing with f(n) growing sufficiently slowly, the entropies of such subshifts are all computable numbers. We ask the following questions : can we reduce the gap between these two behaviors? Could we realize every computable number as the entropy of a low mixing sub- shift? We would like also to talk about two dimensional SFTs. We know that O(log(n))-mixing SFTs have a computable entropy and have a dense set of periodic points. What happen if we take a greater intensity of mixing? Can we produce some O(n)-mixing aperiodic SFT? What are the entropies of O(n)-mixing SFTs ?
Title: Let's compute through infinite time!
Abstract: In this talk, we present infinite time Turing machines (ITTM), from the original definition of the model to some new infinite time algorithms. We will present algorithmic techniques that allow to highlight some properties of the ITTM-computable ordinals. In particular, we will study gaps in ordinal computation times, that is to say, ordinal times at which no infinite time program halts.
Title: Fine-grained complexity of coloring geometric intersection graphs.
Abstract: We are interested in the following problem: given a collection of n convex objects in R^d and an integer k, can we color its intersection graph properly with k colors (i.e., objects with non-empty intersection get different colors). Here we think of k as a function of n, it can be constant, linear, or anything in between. From an application of appropriate separator theorem it follows that if the input objects are fat (i.e., have bounded diameter/width ratio), then this problem can be solved in time n^{O(n^{1-1/d} k^{1/d})}, even if we are given the intersection graph without the geometric representation. In particular, if we are given a unit disk intersection graph, with gives us a n^{O(sqrt(nk))} algorithm. We present a lower bound showing that the algorithm solving the problem for unit disk graph, even with a given representation, in time 2^{o(sqrt(nk))} would contradict the ETH. Then we generalize this result in two ways. First, we consider intersections of unit balls in d-space, and show that an algorithm working in time 2^{O(n^{1-1/d-delta} k^{1/d})} for any delta strictly positive, contradicts the ETH. On the other hand, we show that the lower bound generalized to many other fat convex objects, like polygons, or objects with boundary given by a smooth curve. Finally, we show that the fatness is indeed a crucial assumption. We prove that an algorithm coloring intersection graphs of horizontal and vertical segments with 6 colors in time 2^{o(n)}, contradicts the ETH.
Title: Deterministic Isolation for Space-Bounded Computation
Abstract: Isolation is the process of singling out a solution to a problem that may have many solutions. It plays an important role in the design of efficient parallel algorithms as it ensures that the various parallel processes all work towards a single global solution rather than towards individual solutions that may not be compatible with one another. For example, the best parallel algorithms for finding perfect matchings in graphs hinge on isolation for this reason. Isolation is also an ingredient in some efficient sequential algorithms. For example, the best running times for certain NP-hard problems like finding hamiltonian paths in graphs are achieved via isolation. All of these algorithms are randomized, and the only reason is the use of the Isolation Lemma -- that for any set system over a finite universe, a random assignment of small integer weights to the elements of the universe has a high probability of yielding a unique set of minimum weight in the system. For each of the underlying problems it is open whether deterministic algorithms of similar efficiency exist. This talk is about the possibility of deterministic isolation in the space-bounded setting. The question is: Can one always make the accepting computation paths of nondeterministic space-bounded machines unique without changing the underlying language and without blowing up the space by more than a constant factor? Or equivalently, does there exist a deterministic logarithmic space mapping reduction from directed st-connectivity to itself that transforms positive instances into ones where there is a unique path from s to t? I will present some recent results towards a resolution of this question, obtained jointly with Gautam Prakriya. Our approach towards a positive resolution can be viewed as derandomizing the Isolation Lemma in the context of space-bounded computation.
Title: Universal computation and unpredictability in symbolic systems
Abstract: A system is said to be Turing-universal if it is able to simulate arbitrary computation in some sense. The practical consequence is that predicting the future behaviour of the system is difficult or impossible: P-complete for bounded time prediction, undecidable for unbounded time prediction. The proof proceeds by reduction to classical problems on Turing machine. Naturally, the prediction problem being considered depends on how exactly computation is simulated inside the system, which can lead to various (not so universal) relevant notions of Turing-universality. I will give an overview of various forms of Turing-universality in two symbolic systems: cellular automata and Langton's insects. Cellular automata are Turing-universal for most natural definitions of this notion, which means that all relevant prediction problems are difficult or undecidable. Still, the wide variety of tools and constructions needed for these results by many different authors suggest that the situation could be different. More concretely, it is conjectured that some but not all of these constructions fail with additional restrictions on the system: for example surjective cellular automata are Turing-universal in the classical sense but maybe not on average. A similar phenomenon occurs in Langton's insects, a family of simple bidimensional Turing machines generalising Langton's ant. A long-standing conjecture states that these systems present highly complex but ultimately periodic (and thus predictable) behaviours on finite configurations. On periodic configurations, however, we have a form of Turing-universality and a difficult prediction problem. It is hard to argue which notion is most "natural" and we have to accept a more nuanced picture. Parts of this talk are joint works with Mathieu Sablik; Martin Delacourt; and Anahi Gajardo, Diego Maldonado, and Andrés Moreira.
Title: Every planar triangle-free graph is intersection of segments with three slopes
Abstract:We will present the proof of the above theorem, which partially answers a question raised by De Fraysseix and Ossona de Mendez. Their open problem is, "Is every $k$-colorable planar graph the intersection graph of segments using $k$ slopes ?". It was known to hold for $k=2$. Here we prove the case $k=3$. The case $k=4$ is open and is also known as West's conjecture. As in these intersection models, parallel segments are expected to be pairwise disjoint, this conjecture generalizes both the 4-color theorem and the fact that every planar graph is an intersection graph of segments. A crucial point in our proof is the use of a system of linear equations, which provides a scheme of the solution. It is shown that this system always has a (unique) solution by studying the perfect matchings of some related planar graph. At the end of the talk we will briefly discuss how West's conjecture could be tackled using a similar approach.
Title: Substitutions et calculabilité.
Abstract: Nous considérons des mots ou des pavages obtenus en itérant une composition infinie de substitutions. Une substitution est une règle qui remplace des lettres par des mots (qui peuvent être multidimensionnels), ou des tuiles par des unions de tuiles. Plusieurs notions d'effectivité existent dans ce contexte comme la calculabilité des mesures invariantes, ou la calculabilité du langage. Nous comparerons ces notions, et considérerons en particulier le cas des pavages planaires et des mots sturmiens multidimensionnels. Il s'agit d'un travail en cours avec Th. Fernique et M. Sablik.
Title: Domination in tournaments, an application of sparse VC-dimension.
Abstract: A classical parameter in tournaments (orientations of complete graphs) is the minimum size of a dominating set (set of vertices reaching every vertex at distance at most 1). In general tournaments, a minimum DS has size at most ceiling(log n) and random tournaments have DS at least clog n. The complexity of finding a minimum size DS in a tournament is therefore quasi polynomial, and Megiddo and Vishkin showed that it is polytime solvable iff SAT has c^sqrt(v) time algorithm. A natural question to adress is then to ask for the size of DS when we restrict ourselves to any strict class of tournaments (where class is understood as closed under subtournament, and strict being not the class of all tournaments). Here is a recent conjecture proposed by Hehui Wu: Every strict class of tournaments have bounded domination. This very bold conjecture has a direct corollary: computing domination number in strict classes is in P. Surprisingly it seems that this question was not adressed before, which can be explained in two ways: a) there is some well-known counterexample (but not by us) b) nobody dared to pose it before. The first feeling is that this statement should be very false since it amounts to say the following: given some arbitrary tournament H, the class of tournaments not inducing H has bounded domination (let us say that a tournament H with this property is "good"). It seems indeed very unlikely that every tournament H is good. However, a direct adaptation of a proof of Alon, Brightwell, Kierstead, Kostochka and Winkler about majority tournaments gives the following striking fact: Theorem 1: Every tournament H which can be partitioned into two transitive tournaments is good. The proof of Theorem 1 relies on the fact that tournaments are dense structures and, crucially, that the neighborhoods of any tournament excluding H has bounded Vapnik-Cervonenkis dimension. There is some magic at work here since this result says that if H consists of two disjoint transitive tournaments of size 1000 and filled between them with edges with random orientations, then H is good. Indeed, the crucial point here is bounded VC-dimension, and forbidding any H which has no such partition would result in a class of tournaments with unbounded VC-dimension. In fact, a reasonable guess would be that the only good tournaments are the one satisfying the hypothesis of Theorem 1. This is the motivation of our work, which make one step in the direction of Wu's conjecture: Theorem 1: There exists a good tournament H which cannot be partitioned into two transitive tournaments. The price to pay for this modest step is quite high, but uses a tool which is by itself interesting: the usual application of VC-dimension involves that "shattered sets" are bounded in size, but as mentioned before we do not have this property any more. Instead we overcome this difficulty by arguing that shattered sets are either dense (in which case we get structure and bounded domination) or sparse (in which case we can conclude just by strenghtening the usual tools in VC-dimension). The main goal of this talk is to highlight the use of "sparse VC-dimension". Joint work with Maria Chudnovsky, Ringi Kim, Chun-Hung Liu and Paul Seymour. Addendum: Tuesday 4th May. The conjecture is indeed false, I will provide a counterexample.
Title: Graph limits and extremal combinatorics.
Abstract: Theory of combinatorial limits has opened new links between analysis, combinatorics, computer science, group theory and probability theory. In this theory, large dense graphs are represented by an analytic object called a graphon. Motivated by problems in extremal graph theory, we will focus on graphons that are uniquely determined by finitely many density constraints, so-called finitely forcible graphons. Lovasz and Szegedy initiated a systematic study of such graphons and conjectured that all such graphons must have a simple structure. On the contrary, we will show that finitely forcible graphons can contain any computable graphon as a subgraphon. Our result provides a unified framework for constructing complex finitely forcible graphons, which includes many earlier ad hoc constructions. The talk is based on joint work with Jacob Cooper and Taisa Martins. The presentation will be self-contained and no previous knowledge of graph limits will be assumed.
Title: Une caractérisation de type "local to global" pour les graphes de Helly.
Abstract: Les graphes de Helly sont définis par la propriété suivante: pour toute famille de boules qui s'intersectent deux à deux, il existe un sommet qui appartient à toutes les boules (autrement dit, la famille des boules du graphe a la propriété de Helly). Cette classe de graphe est assez large puisque tout graphe $G$ peut être plongé isométriquement dans un graphe de Helly et on peut parler d'"enveloppe de Helly" de $G$: c'est le plus petit graphe de Helly dans lequel on peut plonger $G$ isométriquement. Dans cet exposé, je vous présenterai quelques résultats existants et d'autres qu'on a obtenu sur cette classe de graphes. En particulier, je parlerai d'une caractérisation de ces graphes de type "local-to-global": les graphes de Helly sont les graphes dont la famille des cliques satisfait la propriété de Helly et dont le complexe de cliques est simplement connexe.
Title: Drawing graphs with few slopes.
Abstract: The slope-number of a graph $G$ is the minimum number of slopes needed to draw $G$ in the plane such that all edges are straight-line segments. For natural reasons one usually tries to bound the slope number by a function of the maximum degree of $G$. I will give a little survey about different results on slope number of graphs, planar graphs, and outerplanar graphs (where such topological properties of the graph are also required to be satisfied by the drawing). Finally, I will present a couple of new results on single-bend drawings of general, planar, and outerplanar graphs, i.e., here edges in the drawing are allowed to turn once. Joint with Bartosz Walczak.
Title: Time and Homonyms Considerations over Community Protocols.
Abstract: Guerraoui and Ruppert introduced the model of Community Protocols. This Distributed System works with agents having a finite memory and unique identifiers (the set of identifiers being ordered). Each agent can store a finite number of identifiers they heard about. The interactions are asynchronous and pairwise, following a fair scheduler. The computation power of this model is fully characterized: it corresponds exactly to what non deterministic Turing Machines can compute on a space $O(n\log n)$. In this talk, I will focus on two restrictions of the model: The first is what happens when agents may share identifiers, the population admitting homonyms. I will introduce a hierarchy, with characterizations depending on the rate of unique identifiers present in the population. The main result is that with log n identifiers, a Turing Machine with a polylogarithmic space can be simulated. The second consider the following time restriction: what can be computed in a polylogarithmic number of parallel interactions. This version is not yet characterized, but I will provide some impossibility results, some computable protocols, and I will give the tighter bound we found.
Title: The Alternating Stock Size Problem and the Gasoline Puzzle.
Abstract:Given a set $S$ of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the ``Stock Size Problem" and showed that it can be approximated to within $3/2$. They also showed that an approximation ratio of $2$ can be achieved via several simple algorithms. We consider a related problem, which we call the ``Alternating Stock Size Problem", where the number of positive and negative integers in the input set $S$ are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple $2$-approximations. We show that it can be approximated to within $1.79$. Then we show that this problem is closely related to an optimization version of the Gasoline Puzzle due to Lovasz, in which we want to minimize the size of the gas tank necessary to go around the track. We give a $2$-approximation for this problem, based on rounding an LP relaxation whose feasible solutions are convex combinations of permutation matrices. This is joint work with Heiko Roeglin (Universitaet Bonn) and Johanna Seif (ENS Lyon).
Title: "The ideal of orthogonal representations of a graph"
Abstract: We study orthogonal representations of simple graphs $G$ in $\mathbb R^d$ from an algebraic perspective in case $d=2$. Orthogonal representations of graphs, introduced by Lov\'asz, are maps from the vertex set to $\mathbb R^d$ where non-adjacent vertices are sent to orthogonal vectors. We exhibit algebraic properties of the ideal generated by the equations expressing this condition and deduce geometric properties of the variety of orthogonal embeddings for $d=2$ and $\mathbb R$ replaced by an arbitrary field. In particular, we classify when the ideal is radical and provide a reduced primary decomposition if $\sqrt{−1} \notin K$. In particular, this applies to the motivating case $K=R$.
For any aditional information, contact me through my e-mail adress in my webpage http://perso.ens-lyon.fr/sebastian.barbieri/.