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

IEEE Transactions on Information Theory

Chain Independence and Common Information

Konstantin Makarychev, Yury Makarychev

Published Jul 10, 2012• 2 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2012.2196022

Related papers

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

László Csirmaz

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$.

arXiv:2306.14718•Jun 26, 2023•2 citations

Assisted common information: Further results

Vinod M. Prabhakaran, Manoj M. Prabhakaran

We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.

arXiv:1105.6163•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•7 citations

Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation

Lei Yu, Houqiang Li, Chang Wen Chen

In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.

arXiv:1610.09289•Oct 28, 2016•19 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

On the Relation Between the Common Information Dimension and Wyner Common Information

Osama A. Hanna, Xinlin Li, Suhas N. Diggavi +1 more

In this paper, we are interested in the regime where the common information between two Gaussian random vectors$(X, Y)$can be (or can approach) infinity. We ask two main questions: what is the rate of growth for common information from a finite to an infinite number of bits, as the dependency between the variables increases? and how well can we “approximately” simulate a pair of random variables$(X, Y)$with infinite common information using a finite number of shared bits? We analytically prove that the answer to both of these questions depends on the common information dimension$d(X, Y)$between$X$and$Y$, that we introduced in our recent work [1]. Our work characterizes in a closed form the asymptotic behaviors, by building a connection to singular values associated with the covariance matrix$\Sigma$of$(X, Y)$. We conclude the paper by providing numerical evaluation results that indicate fast convergence to the asymptotic regime.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•2 citations

Zero-error information and applications in cryptography

Stefan Wolf, J. Wultschleger

In analogy to the zero-error variant of the channel capacity, the zero-error information between two random variables is defined. We show that our definition is natural in the sense that the representation of the channel capacity with respect to mutual information carries over to the zero-error variants of the quantities. It is shown that the new notion, together with two operators introduced in the same context, namely the common random variable of two random variables and the dependent part of a random variable with respect to another, is useful for giving characterizations of the possibility of realizing cryptographic tasks - such as bit commitment, coin tossing, or oblivious transfer - from correlated pieces of information.

Manufacturing Engineer•Apr 6, 2005•48 citations
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.
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 presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.
In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.
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).
In this paper, we are interested in the regime where the common information between two Gaussian random vectors(X,Y)(X, Y)(X,Y)can be (or can approach) infinity. We ask two main questions: what is the rate of growth for common information from a finite to an infinite number of bits, as the dependency between the variables increases? and how well can we “approximately” simulate a pair of random variables(X,Y)(X, Y)(X,Y)with infinite common information using a finite number of shared bits? We analytically prove that the answer to both of these questions depends on the common information dimensiond(X,Y)d(X, Y)d(X,Y)betweenXXXandYYY, that we introduced in our recent work [1]. Our work characterizes in a closed form the asymptotic behaviors, by building a connection to singular values associated with the covariance matrixΣ\SigmaΣof(X,Y)(X, Y)(X,Y). We conclude the paper by providing numerical evaluation results that indicate fast convergence to the asymptotic regime.
In analogy to the zero-error variant of the channel capacity, the zero-error information between two random variables is defined. We show that our definition is natural in the sense that the representation of the channel capacity with respect to mutual information carries over to the zero-error variants of the quantities. It is shown that the new notion, together with two operators introduced in the same context, namely the common random variable of two random variables and the dependent part of a random variable with respect to another, is useful for giving characterizations of the possibility of realizing cryptographic tasks - such as bit commitment, coin tossing, or oblivious transfer - from correlated pieces of information.