Information theoretic results on exact distributed simulation and information extraction
Abstract/Contents
- Abstract
- In the first part of the thesis we will introduce the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables $(X, Y)$. We introduce the quantity $G(X; Y)=\min_{X\to W\to Y}H(W)$ as a natural bound on the exact common information. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of correlated sources $(X, Y)$. We give a multiletter characterization for it as the limit $\Gbar(X; Y)=\lim_{n\to\infty}(1/n)G(X^n; Y^n)$. While in general $\bar{G}(X; Y)$ is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We then discuss the computation of $G(X; Y)$. In the second part, we will introduce a conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let $(X, Y)$ be a doubly symmetric binary source with cross-over probability $\alpha$. For any boolean function $b:\{0,1\}^n\to \{0,1\}$, we conjecture that $I(b(X^n); Y^n)\le 1-H(\alpha)$. While the conjecture remains open, we provide substantial evidence supporting its validity.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2014 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Kumar, Gowtham Ramani |
|---|---|
| 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 | Gowtham Ramani Kumar. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2014. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2014 by Gowtham Kumar Ramani Kumar
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...