Special: Mary Wootters

Suprema of stochastic processes, geometry, and applications

Mary Wootters

Department of Computer Science, Carnegie-Mellon University

Date and time: 

Friday, November 13, 2015 - 3:00pm

Location: 

ECCR 245

Abstract: 

Bounding the supremum of a stochastic process is a problem that shows up in many applications.  Concretely, if X_t is a collection of random variables indexed by a set T, how large is the expectation E \sup_{t \in T} X_t?   In this talk, we’ll discuss three application areas --- signal processing, recommendation engines, and communication --- where this problem arises and where the set T is high-dimensional and complicated.  In such cases, techniques from high-dimensional probability theory can bound the stochastic process in terms of the geometry of T.  We’ll show how to apply such techniques in each of these areas; punchlines include the best known fast Johnson-Lindenstrauss transforms, efficient algorithms for quantized matrix completion, and the answers to some long-standing open combinatorial problems about list-decodable codes.