Lower bounds on the time of probabilistic on-line simulations
Ramamohan Paturi, Janoš Šimon · 1983
We study probabilistic on-line simulators for several machine models (or memory structures). The simulators have a more constrained access to data than the virtual machines, but are allowed to use probabilistic means to improve average access time. We show that in many cases coin tosses can not make up for inadequate access.