#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Ball, Liu, Mazor and Pass [BLMP23] proved that the existence of key-agreement protocols is equivalent to a certain estimate of interactive Kolmogorov complexity being in ioBPP. In the previous talk we stated the problem, explained that this estimation problem is decidable, and proved the backward impliciation (in the contra-positive, breaking a specific protocol provides an ioBPP algorithm for the estimation problem). In this talk we will briefly repeat everything and prove the forward implication (again in the contra-positive, with an ioBPP algorithm of the estimation problem we can break each protocol).

Notes: https://arxiv.org/pdf/2504.16311
The previous talk: https://www.youtube.com/watch?v=D1GdCXak0Nw

➰ ВК