The Complexity of Distributions
Speaker: Emanuele Viola , Northeastern U.Contact:
Date: March 1 2011
Time: 4:15PM to 5:15PM
Host: Scott Aaronson, CSAIL, MIT
Be Blackburn , 3-6098, email@example.comRelevant URL:
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