yesterday's talk

[Alexander Shen]

https://youtu.be/TsktkrRWgd8 <https://youtu.be/TsktkrRWgd8>

Revisiting Kolmogorov complexity: universality or optimality
(Kozachinskiy, Shen) 1965 Kolmogorov paper defined Kolmogorov complexity
in terms of an optimal algorithm that makes the complexity function
minimal. But earlier in 1964 Solomonoff considered a smaller class of
universal algorithms that can simulate any algorithm if a suitable
prefix is added. Does it matter? We show that for plain, conditional
plain and prefix complexity this leads to exactly the same class of
complexity functions, but for conditional prefix complexity this is not
clear...

[Alexander Shen]

will be soon here: https://youtu.be/Cx7bp86wSNg

Bruno Bauwens: paper with Bruno Loff, now in
https://arxiv.org/abs/2504.16311 (2nd iteration)

Ball, Liu, Mazor and Pass proved that the existence of key-agreement
protocols is equivalent to the hardness of a certain problem about
interactive Kolmogorov complexity. We generalize the statement and give
a short proof of the difficult implication.