14 papers
Online Metric TSP: Beyond the Barrier
Yossi Azar, Debmalya Panigrahi, Or Vardi
We study an online variant of the Traveling Salesperson Problem (TSP) in which points arrive sequentially and must be inserted into an evolving tour. In the classical setting w…
Hallucination Rates in Language Generation
Debmalya Panigrahi, Fan Wei, Ian Zhang
Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based…
Stochastic Caching via Subset Entropy
Ravi Kumar, Roie Levin, Joseph +2
A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-ma…
Selectivity Estimation for Linear Queries via Online Learning
Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy
Learning-based approaches for selectivity estimation in databases have gained significant traction in recent years. However, theoretical studies of these learning-based approaches…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
Learning-Augmented Algorithms for -median via Online Learning
Anish Hebbar, Rong Ge, Amit Kumar +1
The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introd…