Max Ovsiankin

activity

20222026

most citedStreaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

2 citations · 3 across the 4 of their papers we have counts for

collaborators

Showing 2023Show all

2 papers · 1 filter

cs.DS2023★ 1 cited

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…

math.FA2023

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms

Naren Sarayu Manoj, Max Ovsiankin

Given a matrix $A \in R^{k \times n}$ , a partitioning of $[k]$ into groups $S_{1}, \dots, S_{m}$ , an outer norm $p$ , and a collection of inner norms such that either $p…