3 papers
math.PR2026
Sofic measures
Marie-Pierre Béal, Vincent Jugé, Jean Mairesse +1
Sofic measures, also known as hidden Markov measures, have been extensively studied. In this paper, we survey some equivalent definitions of this notion and improve a bound for dec…
cs.DS2025
Grandchildren-weight-balanced binary search trees
Vincent Jugé
We revisit weight-balanced trees, also known as trees of bounded balance. This class of binary search trees was invented by Nievergelt and Reingold in 1972. Such trees are obtained…
quant-ph2025
Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista +2
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The correspond…