For more information about this meeting, contact Stephen Simpson.

Title: | Everywhere complex sequences and the probabilistic method |

Seminar: | Logic Seminar |

Speaker: | Alexander Shen, Laboratoire J.-V. Poncelet, Marseille, France |

Abstract Link: | http://www.mccme.ru/lifr/pers/shen.htm |

Abstract: |

Let c be a positive constant which is < 1. One can show that there exists an
"everywhere complex" bit sequence (= "Levin sequence") omega
such that every substring of omega of length n has complexity
at least c n - O(1). There are several ways to prove the existence of
such a sequence (a complexity argument; application of Lovasz Local
Lemma, and some others). S. Simpson asked whether there exists an
algorithm that produces such a sequence when supplied with a Martin-L"of random oracle. Recently A. Rumyantsev gave a negative answer to
this question. We discuss this and related results. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 04 / 06 / 2010 |

Time: | 02:30pm - 03:45pm |