Everywhere complex sequences and the probabilistic method

Andrey Yu. Rumyantsev
The main subject of the paper is everywhere complex sequences. An everywhere complex sequence is a sequence that does not contain substrings of Kolmogorov complexity less than alpha n-O(1) where n is the length of the substring and alpha is a constant between 0 and 1. First, we prove that no randomized algorithm can produce an everywhere complex sequence with positive probability. On the other hand, for weaker notions of everywhere complex sequences the situation...