Andrei Romashchenko talk on March 24

[Andrei Romashchenko]

On March 24 at 16:30 CET (18:30 MSK), we have Andrei Romashchenko's talk "On the reduction of Kolmogorov complexity by relativization".

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

Alexander Shen asked the following question: let us have a tuple of strings x_1,...,x_n and their Kolmogorov complexities  v=(C(x_1),...,C(x_n)). For every string y we get the values of conditional complexities  w=(C(x_1|y),...,C(x_n|y)). Which values w of conditional complexities can we obtain? Can we, for example, find a y such that each value C(x_i|y) is (approximately) a half of C(x_i)?

We show that the answer to the last question is positive for n=1 (trivial) and for n=2 (can be proven with Muchnik's theorem on condtional descriptions or with Shen's topological argument).

For n=3, the answer is negative: there exists a triple (x_1, x_2, x_3) such that C(x_1)=2n, C(x_2)=2n, C(x_3)=3n, and there is no y such that C(x_1|y)=n, C(x_2|y)=n, C(x_3|y)=1.5n. This negative result follows from combinatorial properties of discrete projective planes over prime fields (Bourgain, Katz, Tao).