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.