24 citations · 52 across the 10 of their papers we have counts for
6 papers · 1 filter
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng
We show that any randomized first-order algorithm which minimizes a -dimensional, -Lipschitz convex function over the unit ball must either use bits of memory or…
Near Optimal Memory-Regret Tradeoff for Online Learning
Binghui Peng, Aviad Rubinstein
In the experts problem, on each of days, an agent needs to follow the advice of one of ``experts''. After each day, the loss associated with each expert's advice is reveale…
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Binghui Peng, Aviad Rubinstein
Dynamic algorithms come in three main flavors: (insertions-only), (deletions-only), or (both inser…
Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binghui Peng +1
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive onl…
Tight Bounds for Online Edge Coloring
Ilan Reuven Cohen, Binghui Peng, David Wajc
Vizing's celebrated theorem asserts that any graph of maximum degree admits an edge coloring using at most colors. In contrast, Bar-Noy, Naor and Motwani showed over a qu…
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang +3
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive on…