3 papers
cs.CC2025
Space-bounded online Kolmogorov complexity is additive
Bruno Bauwens, Maria Marchenko
The even online Kolmogorov complexity of a string is the minimal length of a program that for all , on input outputs $…
cs.CC2025
Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
Bruno Bauwens, Bruno Loff
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 genera…
cs.DS2024
Online matching games in bipartite expanders and applications
Bruno Bauwens, Marius Zimand
We study connections between expansion in bipartite graphs and efficient online matching modeled via several games. In the basic game, an opponent switches {\em on} and {\em off} n…