[edit]

# Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

*Proceedings of Thirty Fifth Conference on Learning Theory*, PMLR 178:3070-3093, 2022.

#### Abstract

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 approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.