PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Everywhere complex sequences and forbidden patterns
Seminar:Logic Seminar
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 substrings.) 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

Room Number:MB315
Date:03 / 02 / 2010
Time:02:30pm - 03:45pm