309 citations · 1.1k across the 60 of their papers we have counts for
67 papers
Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, Nitika Saran +3
In a landmark 1981 paper, Valiant and Brebner gave birth to the study of oblivious routing and, simultaneously, introduced its most powerful and ubiquitous method: Valiant load bal…
U-Calibration: Forecasting for an Unknown Agent
Robert Kleinberg, Renato Paes Leme, Jon Schneider +1
We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility…
Non-Stochastic CDF Estimation Using Threshold Queries
Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg +1
Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a…
Online Convex Optimization with Unbounded Memory
Raunak Kumar, Sarah Dean, Robert Kleinberg
Online convex optimization (OCO) is a widely used framework in online learning. In each round, the learner chooses a decision in a convex set and an adversary chooses a convex loss…
Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
Raunak Kumar, Robert Kleinberg
Bandits with knapsacks (BwK) is an influential model of sequential decision-making under uncertainty that incorporates resource consumption constraints. In each round, the decision…
Individual Fairness in Prophet Inequalities
Makis Arsenis, Robert Kleinberg
Prophet inequalities are performance guarantees for online algorithms (a.k.a. stopping rules) solving the following "hiring problem": a decision maker sequentially inspects candida…