23 citations · 29 across the 9 of their papers we have counts for
14 papers
Efficient Caching with Reserves via Marking
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis -- including potential functions…
Caching with Reserves
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Caching is a crucial component of many computer systems, so naturally it is a well-studied topic in algorithm design. Much of traditional caching research studies cache management…
Margin-Independent Online Multiclass Learning via Convex Geometry
Guru Guruganesh, Allen Liu, Jon Schneider +1
We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which se…
Scheduling with Communication Delay in Near-Linear Time
Quanquan C. Liu, Manish Purohit, Zoya Svitkina +2
We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-…
Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
Rad Niazadeh, Negin Golrezaei, Joshua Wang +2
Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on of…
Contracts under Moral Hazard and Adverse Selection
Guru Guruganesh, Jon Schneider, Joshua Wang
In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical princip…
Recursive Sketches for Modular Deep Learning
Badih Ghazi, Rina Panigrahy, Joshua R. Wang
We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inpu…
On the Computational Power of Online Gradient Descent
Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results impl…
An Optimal Algorithm for Online Unconstrained Submodular Maximization
Tim Roughgarden, Joshua R. Wang
We consider a basic problem at the interface of two fundamental fields: submodular optimization and online learning. In the online unconstrained submodular maximization (online USM…
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
Rad Niazadeh, Tim Roughgarden, Joshua R. Wang
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. Thi…
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, Huacheng Yu
In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the player…
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1
Given a set of numbers, the -SUM problem asks for a subset of numbers that sums to zero. When the numbers are integers, the time and space complexity of -SUM is generally…
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Amir Abboud, Virginia Vassilevska Williams, Joshua Wang
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a ve…
Space-Efficient Las Vegas Algorithms for K-SUM
Joshua Wang
Using hashing techniques, this paper develops a family of space-efficient Las Vegas randomized algorithms for -SUM problems. This family includes an algorithm that can solve 3-S…