3 papers
cs.IT2025
All Kolmogorov complexity functions are optimal, but are some more optimal?
Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
Kolmogorov (1965) defined the complexity of a string as the minimal length of a program generating . Obviously this definition depends on the choice of the programming langu…
cs.NI2024
Efficient Mixed Integer Linear Programming Approaches to Dynamic Path Restoration
Alexander Rubtsov, Bruno Bauwens, Dmitri Shmelkin +2
We consider the problem of single link failure in an elastic optical network, (also known as flex-grid WDM network). The task is to reroute optical connections that go through the…
cs.IT2020
Inequalities for space-bounded Kolmogorov complexity
Bruno Bauwens, Peter Gács, Andrei Romashchenko +1
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples o…