Algorithms for Multi-Dimensional Data via Sketches.

We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε^{(d-1)/2}) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a corresponding upper bound on the total combinatorial complexity has been open for over 40 years. In 2017, we made a significant step forward towards this objective, obtaining a bound that is suboptimal by a factor of O(log^{(d-1)/2}(1/eps)). In SODA 2020, we improve this to an asymptotically optimal bound of O(1/ε^{(d-1)/2}). During this talk, I'll explain these two results, which are based on a layered version of the economical cap covering using Macbeath regions, a relationship between ε-width caps of a convex body and its polar, and the witness collector technique.

I will prove a classical result in robust statistics for Median-of-means estimators which can be performed using either the VC dimension or the Rademacher complexities. The aim is to recover the complexity that we would have obtain if all the data were Gaussian variables; that is the Gaussian mean width. We will see some pros and cons of the two VC and Rademacher complexities.

Geometric set-cover/hitting-set problems arise naturally in several basic settings, and therefore the problem of computing small set covers (and hitting sets) has been studied extensively. A common first step in solving such optimization problems is to formulate and solve the corresponding covering/packing LP to get a fractional solution. Then the task reduces to constructing an integer solution from this fractional solution. In this talk, I will present a new simple iterative randomized rounding scheme that gives optimal approximation bounds, within constant factors, for many well-studied geometric systems. It will illustrate a fruitful interaction of sampling theory, algorithms, combinatorics and geometry.