CSAIL Event Calendar: Previous Series

Conditional Computational Entropy, or Towards Separating Pseudoentropy from Compressibility

Speaker: Leonid Reyzin , Boston University
Date: March 11 2008
Time: 4:15PM to 5:25PM
Location: 32-155
Host: Silvio Micali, MIT

Computational entropy measures the amount of randomness a distribution appears to have to a computationally bounded observer. It is an open question whether two definitions of this entropy -- the so-called "HILL entropy" (based on indistinguishability from truly random distributions) and "Yao entropy" (based on incompressibility) are equivalent, as they are in the information-theoretic setting. We observe that most of the time the observer has some correlated information, and thus define and study _conditional_ computational entropy. By considering conditional versions of HILL and Yao entropies, we obtain:
-- a separation between conditional HILL and Yao entropies;
-- the first demonstration of a distribution from which extraction techniques based on Yao entropy produce more pseudorandom bits than appears possible by the traditional HILL-entropy-based techniques;
-- a new, natural notion of unpredictability entropy, which, in particular, can handle entropy of singleton distributions, and allows for known extraction and hardcore bit results to be stated and used more generally.

Joint work with Chun-Yuan Hsiao and Chi-Jen Lu.

See other events that are part of Theory Colloquium Spring 2008

See other events happening in March 2008