Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.14718

A short proof of the Gács--Körner theorem

László Csirmaz

Published Jun 26, 2023• 2 citations
arXivHTMLPDF

Abstract

We present a short proof of a celebrated result of Gács and Körner giving sufficient and necessary condition on the joint distribution of two discrete random variables $X$ and $Y$ for the case when their mutual information matches the extractable (in the limit) common information. Our proof is based on the observation that the mere existence of certain random variables jointly distributed with $X$ and $Y$ can impose restriction on all random variables jointly distributed with $X$ and $Y$.

DOI
10.48550/arxiv.2306.14718

Related papers

Chain Independence and Common Information

Konstantin Makarychev, Yury Makarychev

We present a new proof of a celebrated result of Gács and Körner that the common information is far less than the mutual information. Consider two sequences$\alpha_{1},\ldots\alpha_{n}$and$\beta_{1},\ldots,\beta_{n}$of random variables, where pairs$(\alpha_{1},\beta_{1}),\ldots, (\alpha_{n},\beta_{n})$are independent and identically distributed. Gács and Körner proved that it is not possible to extract “common information” from these two sequences unless the joint distribution matrix of random variables$(\alpha_{i},\beta_{i})$is a block matrix.

IEEE Transactions on Information Theory•Jul 10, 2012•2 citations

A Collection of Probabilistic Hidden-Variable Theorems and Counterexamples

Patrick Suppes, J. Acácio de Barros, Gary Oas

The purpose of this article is to formulate a number of probabilistic hidden-variable theorems, to provide proofs in some cases, and counterexamples to some conjectured relationships. The first theorem is the fundamental one. It asserts the general equivalence of the existence of a hidden variable and the existence of a joint probability distribution of the observed quatities, whether finite or continuous.

arXiv:quant-ph/9610010•Oct 8, 1996•10 citations

Common Information of Two Correlated Random Variables

H. Yamamoto

Two kinds of common information are defined for two correlated random variables, and they are represented by single letter characterizations.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

Assisted Common Information With an Application to Secure Two-Party Sampling

Vinod M. Prabhakaran, Manoj Prabhakaran

An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).

arXiv:1002.1916•IEEE Transactions on Information Theory•Apr 7, 2014•48 citations

Some Results on Distributed Source Simulation with no Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•0 citations

Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources

Salman Beigi, Omid Etesami, Amin Gohari

A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to $s$ “nondegenerate” dice that are $c$-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if $s<c$. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions complement each other in the nondegenerate cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs $(a_1, b_1), (a_2, b_2), \ldots$ distributed between two parties, where the first party receives $a_i$'s and the second one receives $b_i$'s. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (nondistributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from independently and identically distributed sources to adversarial sources.

arXiv:1412.6641•SIAM Journal on Computing•Jan 1, 2017•8 citations
We present a short proof of a celebrated result of Gács and Körner giving sufficient and necessary condition on the joint distribution of two discrete random variables XXX and YYY for the case when their mutual information matches the extractable (in the limit) common information. Our proof is based on the observation that the mere existence of certain random variables jointly distributed with XXX and YYY can impose restriction on all random variables jointly distributed with XXX and YYY.
We present a new proof of a celebrated result of Gács and Körner that the common information is far less than the mutual information. Consider two sequencesα1,…αn\alpha_{1},\ldots\alpha_{n}α1​,…αn​andβ1,…,βn\beta_{1},\ldots,\beta_{n}β1​,…,βn​of random variables, where pairs(α1,β1),…,(αn,βn)(\alpha_{1},\beta_{1}),\ldots, (\alpha_{n},\beta_{n})(α1​,β1​),…,(αn​,βn​)are independent and identically distributed. Gács and Körner proved that it is not possible to extract “common information” from these two sequences unless the joint distribution matrix of random variables(αi,βi)(\alpha_{i},\beta_{i})(αi​,βi​)is a block matrix.
An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution pUV⊗np_{UV}^{\otimes n}pUV⊗n​, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to pXY⊗np_{XY}^{\otimes n}pXY⊗n​. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X−U−V−YX-U-V-YX−U−V−Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters p,q≤1/2p, q\leq 1/2p,q≤1/2 respectively. While it is trivial that in this case p≤qp\leq qp≤q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to sss “nondegenerate” dice that are ccc-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if s<cs<cs<c. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions complement each other in the nondegenerate cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs (a1,b1),(a2,b2),…(a_1, b_1), (a_2, b_2), \ldots(a1​,b1​),(a2​,b2​),… distributed between two parties, where the first party receives aia_iai​'s and the second one receives bib_ibi​'s. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (nondistributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from independently and identically distributed sources to adversarial sources.