31 citations · 50 across the 12 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022★ 2 cited
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…
cs.DS2022
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)…