{"ID":23507366,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20610","arxiv_id":"2609.20610","title":"An $\\tilde Ω(\\log n \\log m)$ Information-Theoretic Lower Bound for Randomized Online Set Cover","abstract":"We show an information-theoretic lower bound of $Ω\\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 \\leq m \\leq 2^n$.","short_abstract":"We show an information-theoretic lower bound of $Ω\\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 \\leq m \\leq 2^n$.","url_abs":"https://arxiv.org/abs/2609.20610","url_pdf":"https://arxiv.org/pdf/2609.20610v1","authors":"[\"Roie Levin\"]","published":"2026-09-17T15:56:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}