Abstracts of the talks:

Nicolas Bédaride

Topological susbtitutions.

A substitution is a morphism of a free monoid defined over a finite alphabet. This map has a fixed point, and one can study the subshift constructed by the action of the shift map on the fixed point. These maps have been studied for a long time with different points of view: combinatorics, ergodic theory. We are mainly interested in tilings and dynamical systems. To a given tiling of the euclidean space we can associate a dynamicam system by the action of the translation group on the tiling. A substitution can be seen as a one dimensional model of the same map. Here we want to do the same thing in dimension two. We define the notion of topological substitution. This notion only depends on the topology of the space. We give conditions on this map to define a tiling of the hyperbolic plane.


Laurent Bienvenu

Randomly-generated fast growing functions.

In classical probability theory, using a random oracle does not help much. Indeed, if a Turing machine using a random oracle is able to compute some set X with positive probability, then X is already computable. However, randomness sometimes helps. A theorem of Martin states that there exists a Turing machine which, with positive probability, generates a fast-growing function (i.e. a function that cannot be dominated by any computable one). The talk will discuss topics related to this fact, such as almost-everywhere domination and Gács's quantitative approach to these questions, and our recent extension of Gács's quantitative approach to these question.


Thomas Fernique

Growth of quasicrystals by a relaxation process.

Tilings are often used as a toy model for quasicrystals, with the ground states corresponding to the tilings satisfying some local properties (matching rules). In this context, a challenging problem is to provide a theory for quasicrystals growth. One of the proposed theories is the relaxation process. One assumes that the entropy of a tiling increases with the number of tilings which can be formed with the same tiles, while its energy is proportional to the ratio of satisfied matching rules. Then, by starting from an entropically stabilized tiling at high temperature and by decreasing the temperature, the phason flips which decrease (resp. increase) the energy would become more and more favoured (resp. inhibited). Ideally, the tiling eventually satisfies all the matching rules, thus shows a quasicrystalline structure. The purpose of this talk is to describe a stochastic process inspired by this and to discuss convergence rates towards ground states. We present experimental results for the Penrose rhomb tiling, which surprisingly shows a rather fast convergence. We also present some theoretical results in a simpler case (co-dimension one tilings).


Mathieu Hoyrup

Randomness, computability and the ergodic decomposition

Given a (computable) dynamical system, we study the algorithmic properties of its invariant measures, namely their computability and the properties of their Martin-Löf random points. My talk will be a survey of some recent results and current open questions.


Dmitry Itsykson

The complexity of inversion of Goldreich's function by backtracking algorithms.

The Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Every Goldreich's function is defined by it's dependency graph G and predicate P. In 2000 O. Goldreich formulated a conjecture that if G is an expander and P is a random predicate of arity d then the corresponding function is one way. In 2005 M. Alekhnovich, E. Hirsch and D. Itsykson proved the exponential lower bound on the complexity of inversion of Goldreich's function based on linear predicate and random graph by myopic bactracking agorithms. In 2009 J. Cook, O. Etesami, R. Miller, and L. Trevisan extended this result for nonliniar predicates. In 2010 Itsykson proved lower bound for drunken backtracking algorithms that invert Goldreich's function with nonlinear P and random G. All above lower bounds are randomized. It will be shown how to prove explicit lower bound based on explicit expanders. Ideas will be demonstrated on the simplified proof of lower bound for myoipic algorithms for linear Goldreich's function. The talk is based on the joint work of the speaker and Dmitry Sokolov.


Roman Kolpakov and Gregory Kucherov

Searching for gapped palindromes.

We study the problem of finding, in a given word, all maximal gapped palindromes verifying two types of constraints, that we call long-armed and length-constrained palindromes. For both classes, we propose algorithms that run in time O(n+S), where S is the number of output palindromes. Both algorithms can be extended to compute biological gapped palindromes within the same time bound.


Alexander Kulikov

Circuit Complexity and Multiplicative Complexity of Boolean Functions.

In this note, we use lower bounds on Boolean multiplicative complexity to prove lower bounds on Boolean circuit complexity. We give a very simple proof of a 7n/3-c lower bound on the circuit complexity of a large class of functions representable by high degree polynomials over GF(2). The key idea of the proof is a circuit complexity measure assigning different weights to XOR and AND gates.


Thierry Monteil

Regularity and induction in symbolic dynamics.

Starting from a simple notion supposed to describe some regularity in an infinite word, i will try to compare what one means by "notion of regularity", and the stability of such a notion by a change of scale, (such a change of scale corresponds to the induction in dynamics, or to return words in combinatorics on words). Depending on the duration of the talk, i will deal with the examples of entropy, uniform recurrence, invariant measures, and ask for similar correspondences in the computational framework.


Mathieu Raffinot

Split decomposition of undirected graphs.

We revisit the problem of designing a linear time algorithm for undirected graph split decomposition that has been first addressed in [E. Dahlhaus, FSTTCS, 1994] and [E. Dahlhaus, Journal of Algorithms 36(2):205-240, 2000]. We present a new and well founded theoretical background for split decomposition (also known as 1-join decomposition) which allows us to clearly design and prove a relatively simple linear-time split decomposition algorithm. Joint work with Pierre Charbit and Fabien de Montgolfier.


Michael Rao

Last Cases of Dejean's Conjecture.

In 1972, Francoise Dejean conjectured that the repetition threshold over a k-letter alphabet is equal to k/(k-1) (except for special cases k=3 and k=4). Dejean's conjecture has been proved for k=2 (Thue 1906), k=3 (Dejean 1972), k=4 (Pansiot 1984), 5<=k<=11 (Moulin Ollagnier 1992), 12<=k<=14 (Mohammad-Noori, Currie 2007), k>=33 (Carpi 2007) and k>=27 (Currie, Rampersad 2009). I will present a proof for 8<=k<=38 using a generalization of Moulin Ollagnier technique. This technique is also used to prove Ochem's stronger version of the conjecture for 9<=k<=38.


Alexander Tiskin

Fast Distance Multiplication of Unit-Monge Matrices.

A matrix is called Monge, if its density matrix is nonnegative. Monge matrices play an important role in optimisation. Distance multiplication (also known as min-plus or tropical multiplication) of two Monge matrices of size n can be performed in time O(n^2). Motivated by applications to string algorithms, we introduce the following subclass of Monge matrices: a matrix is called unit-Monge, if its density matrix is a permutation matrix. We further restrict our attention to a natural subclass that we call simple unit-Monge matrices; under distance multiplication, such matrices form a finite aperiodic monoid with many interesting properties. Previously, we have shown that distance multiplication of simple unit-Monge matrices can be performed in time O(n^{1.5}). Landau conjectured in 2006 that this problem can be solved in linear time. In the current work, we give an algorithm running in time O(n log n), thus approaching Landau's conjecture within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of string and graph algorithms; in particular, we obtain an algorithm for finding a maximum clique in a circle graph in time O(n log^2 n), and a surprisingly efficient algorithm for comparing compressed strings. We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserves further study from both the mathematical and the algorithmic viewpoints. A. Tiskin. Fast distance multiplication of unit-Monge matrices. In Proceedings of ACM-SIAM SODA, pp. 1287-1296, 2010.


Vladimir Zhuravlev

Quasicrystals: grows, form, complexity.

The talk includes the following topics: geometric and arithmetic constructions of quasicrystals, finite and infinite Rauzy fractals, complexity functions and forcing, growth of quasicrystals (dynamics and forms), quasicrystals as infinite Rauzy fractals and their self-similarity.