Theory Day March 2, 2009 - Salil Vadhan

Inaccessible Entropy

In this talk, I will:
- Introduce a new notion of "inaccessible entropy", which measures the infeasibility of randomly sampling from a large subset of a given set of "valid" strings,
- Contrast it with previous computational notions of entropy, and
- Describe applications of this notion to cryptography (specifically to the construction of statistically hiding commitment schemes)

Joint work with Iftach Haitner, Omer Reingold, and Hoeteck Wee.