Information-theoretic limits of distributed randomness generation
Abstract/Contents
- Abstract
- Randomness generation has numerous important applications, for example, in statistical sampling, randomized algorithms and cryptography. In this dissertation, we study randomness generation from an information-theoretic point of view. Extending the seminal work of Knuth and Yao on generating random variables from coin flips, we investigate several multi-terminal randomness generation settings. First we consider the distributed generation setting in which Alice and Bob share a common random source, and each of them would like to generate a random variable such that the two random variables follow a prescribed joint distribution. The goal is to minimize the amount of common randomness needed. We show that for log-concave distributions, the amount of common randomness is within a constant gap of the mutual information. The proof uses a novel construction called dyadic decomposition. We then consider the remote generation setting in which Alice, who knows the chosen distribution, wishes to send a message to Bob to enable him to generate a random variable distributed according to this distribution. We design a scheme that applies to any continuous distribution and establish an upper bound on its expected codeword length using dyadic decomposition. Finally, we consider the one-shot channel simulation setting with unlimited common randomness. We strengthen the result by Harsha et al. using a new strong functional representation lemma, and show that it can be applied in designing schemes for one-shot lossy source coding, and providing a simple proof of the Gelfand-Pinsker theorem for channels with state.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Li, Cheuk Ting |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering. |
| Primary advisor | El Gamal, Abbas A |
| Thesis advisor | El Gamal, Abbas A |
| Thesis advisor | Özgür, Ayfer |
| Thesis advisor | Weissman, Tsachy |
| Advisor | Özgür, Ayfer |
| Advisor | Weissman, Tsachy |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Cheuk Ting Li. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Cheuk Ting Li
Also listed in
Loading usage metrics...