Colloquium

Konstantin Tikhomirov, Carnegie Mellon University

"On the width of random polyhedra"

We consider the problem of estimating the width of a polyhedron defined as the intersection of m i.i.d random affine subspaces of n-dimensional space. Such polyhedra naturally appear in probabilistic analysis of linear programs, as well as in convex geometric analysis as extremizers of various quantities associated with convex sets. For a wide range of parameters m, n, we obtain sharp estimates of the width of the polyhedron in any given direction.

MC 5501