For more information about this meeting, contact Stephen Simpson.
|Title:||Everywhere complex sequences and forbidden patterns|
|Speaker:||Alexander Shen, Laboratoire J.-V.Poncelet, Marseille, France|
|Is there an infinite sequence of bits that is "everywhere complex": every
substring x has complexity at least 0.99|x|-c (where |x| is the
length of x and c is some constant not depending on x)?
(Note that random sequences do not work since they contain all possible
As L. Levin noted, such a sequence indeed exists and can be constructed
by using a Kolmogorov complexity argument. Later M. Ushakov and
A. Rumyantsev found a combinatorial equivalent of this statement and
its relation to the Lovasz Local Lemma. This lemma can be used to prove a
useful generalization of Levin's statement.|
Room Reservation Information
|Date:||03 / 02 / 2010|
|Time:||02:30pm - 03:45pm|