CSAIL Event Calendar: Previous Series

The Complexity of Distributions

Speaker: Emanuele Viola , Northeastern U.
Date: March 1 2011
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT

Complexity theory, with some notable exceptions, typically studies the complexity of computing a function h(x) of a *given* input x. We advocate the study of the complexity of generating -- or sampling -- the output distribution h(x) for random x, given random bits.

In particular, we present first-of-their-kind lower bounds for generating distributions in various restricted computational models, and discuss their implications for extractor constructions and lower bounds for succinct data structures.

See other events that are part of Theory Colloquium 2010/2011

See other events happening in March 2011