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 |
|---|
