Randomization can be as helpful as a glimpse of the future in online computation

Jesper W. Mikkelsen

We provide simple but surprisingly useful direct product theorems for proving lower bounds on online algorithms with a limited amount of advice about the future. As a consequence,…