5 papers
Early science acceleration experiments with GPT-5
Sébastien Bubeck, Christian Coester, Ronen Eldan +11
AI models like GPT-5 are an increasingly valuable tool for scientists, but many remain unaware of the capabilities of frontier AI. We present a collection of short case studies in…
Online 3-Taxi on General Metrics
Christian Coester, Tze-Yang Poon
The online -taxi problem, introduced in 1990 by Fiat, Rabani and Ravid, is a generalization of the -server problem where taxis must serve a sequence of requests in a metr…
Smoothed Analysis of Online Metric Problems
Christian Coester, Jack Umenberger
We study three classical online problems -- -server, -taxi, and chasing size sets -- through a lens of smoothed analysis. Our setting allows request locations to be adver…
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…
Learning-Augmented Priority Queues
Ziyad Benomar, Christian Coester
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements…