Information theoretic results on exact distributed simulation and information extraction

Placeholder Show Content


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.


Type of resource text
Form electronic; electronic resource; remote
Extent 1 online resource.
Publication date 2014
Issuance monographic
Language English


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


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

© 2014 by Gowtham Kumar Ramani Kumar
This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).

Also listed in

Loading usage metrics...