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 |

Abstract: |

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 |