PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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