today's talk video

2 views

Skip to first unread message

Alexander Shen

unread,

Mar 24, 2025, 3:05:19 PMMar 24

to Kolmogorov seminar on complexity

Andrei Romashchenko Imagine we have three strings $x,y,z$; is it possible to find an oracle $A$ that makes the complexity of $x,y,z$ twice smaller. Using a bound about line-points graph for affine plane over Z/pZ, we can see that this is not the case: there exist x,y such that C(x)=C(y)=2n and C(xy)=3n but for every oracle A such that C(x|A)=C(y|A)=n the complexity of C(xy|A) is smaller than 1.5n. Namely, x,y is the random pair (line,point) in this plane