31 citations · 50 across the 12 of their papers we have counts for
4 papers · 1 filter
Dueling Optimization with a Monotone Adversary
Avrim Blum, Meghal Gupta, Gene Li +3
We introduce and study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an…
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension…
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their…
An Optimal Algorithm for Certifying Monotone Functions
Meghal Gupta, Naren Sarayu Manoj
Given query access to a monotone function with certificate complexity and an input , we design an algorithm that outputs a size-$C(f)…