About The Forum
Calendar 2017 Poster Sessions : Information-Theoretic Limits of Randomness Generation
Abstract:
Generation of random variables with prescribed distributions from coin flips arises in applications such as Monte Carlo simulation, randomized algorithms and cryptography. In a seminal paper, Knuth and Yao showed that entropy is the limit on the number of random bits needed for "local" randomness generation. We consider three "remote" one-shot generation settings, namely distributed generation, channel simulation with and without common randomness, and universal remote generation. We show that the amount of randomness needed in each case can again be bounded using information-theoretic quantities. The proofs of these results involve several new techniques, including a dyadic decomposition generation scheme, a new quantity called erosion entropy, and a strong functional representation lemma.
Bio:
Cheuk Ting Li received the B.Sc. degree in mathematics and B.Eng. degree in information engineering from The Chinese University of Hong Kong in 2012, and the M.S. degree in electrical engineering from Stanford University in 2014. He is currently working toward the Ph.D. degree at Stanford University, with expected graduation date of June 2017. His research interests include generation of random variables, one-shot schemes in information theory, wireless communications and information-theoretic secrecy.
Generation of random variables with prescribed distributions from coin flips arises in applications such as Monte Carlo simulation, randomized algorithms and cryptography. In a seminal paper, Knuth and Yao showed that entropy is the limit on the number of random bits needed for "local" randomness generation. We consider three "remote" one-shot generation settings, namely distributed generation, channel simulation with and without common randomness, and universal remote generation. We show that the amount of randomness needed in each case can again be bounded using information-theoretic quantities. The proofs of these results involve several new techniques, including a dyadic decomposition generation scheme, a new quantity called erosion entropy, and a strong functional representation lemma.
Bio:
Cheuk Ting Li received the B.Sc. degree in mathematics and B.Eng. degree in information engineering from The Chinese University of Hong Kong in 2012, and the M.S. degree in electrical engineering from Stanford University in 2014. He is currently working toward the Ph.D. degree at Stanford University, with expected graduation date of June 2017. His research interests include generation of random variables, one-shot schemes in information theory, wireless communications and information-theoretic secrecy.