Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
In this talk, Andrei Romashchenko explores the intriguing question of whether oracle complexity can halve the complexity of multiple strings simultaneously. Delve into a mathematical investigation of three strings x, y, and z, and discover why finding an oracle A that reduces their complexity by half is impossible. Learn how bounds related to line-points graphs for affine planes over Z/pZ demonstrate that for certain strings x and y with complexity C(x)=C(y)=2n and C(xy)=3n, any oracle A that reduces individual complexities to C(x|A)=C(y|A)=n will necessarily make the joint complexity C(xy|A) less than 1.5n. Examine the specific case where x and y represent a random pair of line and point in this plane, providing a concrete example of this complexity phenomenon. This lecture is part of the historic Kolmogorov seminar on computational and descriptional complexity, founded by Kolmogorov himself around 1979.
