6 papers
Universal Connection Schedules for Reconfigurable Networking
Shaleen Baral, Robert Kleinberg, Sylvan Martin +3
Reconfigurable networks are a novel communication paradigm in which the pattern of connectivity between hosts varies rapidly over time. Prior theoretical work explored the inherent…
Improving Pinwheel Density Bounds for Small Minimums
Ahan Mishra, Parker Rho, Robert Kleinberg
The density bound for schedulability for general pinwheel instances is , but density bounds better than can be shown for cases in which the minimum eleme…
Efficient AllReduce with Stragglers
Arjun Devraj, Eric Ding, Abhishek Vijaya Kumar +2
Distributed machine learning workloads use data and tensor parallelism for training and inference, both of which rely on the AllReduce collective to synchronize gradients or activa…
Full Swap Regret and Discretized Calibration
Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor +3
We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embe…
Near-Optimal Algorithms for Omniprediction
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class , simultaneously for every loss function within a class…
Learning in Budgeted Auctions with Spacing Objectives
Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus +3
In many repeated auction settings, participants care not only about how frequently they win but also how their winnings are distributed over time. This problem arises in various pr…