Speaker
Or Zamir
Description
Or Zamir
Abstract: Let $\mathcal{A}$ be an algorithm with expected running time $e^X$, conditioned on the value of some random variable $X$.
We construct an algorithm $\mathcal{A'}$ with expected running time $O\left(e^{E[X]}\right)$, that fully executes $\mathcal{A}$.
In particular, an algorithm whose running time is a random variable $T$ can be converted to one with expected running time $O\left(e^{E[\ln T]}\right)$, which is never worse than $O(E[T])$.
No information about the distribution of $X$ is required for the construction of $\mathcal{A}'$.