The Complexity of Distributions
| Computer Science/Discrete Mathematics Seminar I | |
| Topic: | The Complexity of Distributions |
| Speaker: | Emanuele Viola |
| Affiliation: | Northeastern University |
| Date: | Monday, March 5 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
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. We also discuss connections to succinct data structures and to randomness extractors.