## 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.