10 citations · 17 across the 14 of their papers we have counts for
3 papers · 1 filter
The Randomized -Server Conjecture is False!
Sébastien Bubeck, Christian Coester, Yuval Rabani
We prove a few new lower bounds on the randomized competitive ratio for the -server problem and other related problems, resolving some long-standing conjectures. In particular,…
Competitive Algorithms for Block-Aware Caching
Christian Coester, Roie Levin, Joseph +2
We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evictin…
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Yuval Rabani
In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while att…