talk 9 march

[kozmath]

Dear participants of the Kolmogorov seminar

Next week, we will continue the talk of Alexey Milovanov:

9 March, 18:30 MSK, 16:30 Paris, 12:30 Santiago Zoom:

https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

Limit on the computational power of C-random strings.

Informally, the Kolmogorov complexity of a string x is defined as the minimal length
of a program that outputs x on the empty input. This concept allows us to define the
notion of an individual random string. Specifically, a string x is called random if its
Kolmogorov complexity is at least the length of x. Let R denote the set of
all random strings. A natural question is: how powerful is the oracle R?
For example, what languages belong to P^R?

These and similar questions have been investigated in the works of Allender, Hirahara,
and others. For example, it was shown that for every universal decompressor of plain
complexity U, the class P^{R_U} contains NEXP.

However, no non-trivial upper bounds for P^{R_U} were previously known: it was not
even known whether there is any universal U such that the halting problem does not
belong to P^{R_U}. In this talk, it will be shown that such a U exists, which solves one

of the open questions posed here: https://people.cs.rutgers.edu/~allender/papers/sigact.news.draft.pdf

Best,

Sasha