An $\tilde{\mathrm{\Omega }}(\log n\log m)$ Information-Theoretic Lower Bound for Randomized Online Set Cover

We show an information-theoretic lower bound of $\mathrm{\Omega }\left(\frac{\log n\log m}{\log \log n+\log \log m}\right)$ for online set cover against randomized algorithms, for all sufficiently large $m$ and $n$ satisfying ${\log }^{2}n\le m\le 2^n$.