Coordination Through Shared Randomness

Anand D. Sarwate; Gowtham R. Kurri; Vinod M. Prabhakaran

REVIEW 2 major objections 4 minor 57 references

Coordination Through Shared Randomness

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that with an omniscient coordinator and individually shared randomness, the optimal broadcast rate is a min-max of two mutual information quantities.

desk verdict Strong paper: gives relaxed Wyner's common information an operational interpretation and nails the oblivious-coordinator rate region; worth a serious referee. read the letter →

arxiv 1908.08407 v3 pith:YKPBBYN2 submitted 2019-08-22 cs.IT math.IT

Gowtham R. Kurri , Vinod M. Prabhakaran , Anand D. Sarwate This is my paper · ORCID

classification cs.ITmath.IT MSC 94A1594A1794A29

keywords strongcoordinationsharedrandomnessWyner'scommoninformationrelaxedWynerdistributedsamplingrandombinningchannelresolvabilitytotalcorrelation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how many bits a coordinator must broadcast over a shared link so that a group of processors, each holding a subset of the coordinator's random sources, can output samples from a prescribed joint distribution. The main discovery is an exact single-letter formula for the optimal broadcast rate when the coordinator sees all shared randomness and each processor holds its own private source: the rate is the minimum over auxiliary variables $U$ of $\max\{I(X_1;\ldots;X_t|U), I(X_1,\ldots,X_t;U)\}$, where the first term is Watanabe's total correlation. For two processors this rate equals the fixed point of relaxed Wyner's common information, so the paper gives that optimization a concrete operational meaning as a communication cost. In the oblivious setting, where the coordinator sees none of the shared randomness, the paper gives the full trade-off region between broadcast rate and shared-randomness rates, recovering multi-user Wyner's common information when no shared randomness exists. A sympathetic reader would care because these are rare cases where a distributed-sampling problem yields a closed-form, computable optimum rather than only bounds.

What carries the argument

The load-bearing object is the min-max mutual-information expression $R_{\mathrm{opt}} = \min_{p(u|x_{[1:t]})} \max\{I(X_1;\ldots;X_t|U), I(X_1,\ldots,X_t;U)\}$, together with the two-processor identity $R_{\mathrm{opt}} = C_{\gamma^*}$, where $C_\gamma$ is relaxed Wyner's common information and $\gamma^*$ is its fixed point. The first term, Watanabe's total correlation, measures how much the outputs remain correlated after conditioning on the auxiliary variable; the second term measures how much information the auxiliary variable carries about the joint outputs. Achievability is carried by the Output Statistics of Random Binning (OSRB) framework: random binning indices are split into a common part, distributed to all processors by network-coding XOR, and private parts used jointly by the coordinator and one processor, and OSRB approximation lemmas show the induced output distribution approaches the target. The converse turns on the observation that the conditional mutual information $I(X^n;Y^n|M)$ is not zero, as in Wyner's model, but is upper bounded by the message rate $nR$, forcing the min-max formula.

What would settle it

Find a joint distribution $q_{XY}$ and a sequence of simulation codes whose broadcast rate is strictly below $\min_{p(u|x,y)} \max\{I(X;Y|U), I(X,Y;U)\}$ while achieving vanishing total variation; such a code would refute Theorem 2. Alternatively, compute the fixed point $C_{\gamma^*}$ for a small alphabet exhaustively and verify that no lower-rate protocol exists; a lower-rate protocol is a direct counterexample.

Watch

Extended reading notes

Core claim

The central claim is Theorem 6: with an omniscient coordinator, unlimited individually shared randomness, and $t$ processors, the optimal transmission rate is $R_{\mathrm{Indv}}^{\mathrm{opt}} = \min_{p(u|x_{[1:t]})} \max\{I(X_1;\ldots;X_t|U), I(X_1,\ldots,X_t;U)\}$, where $I(X_1;\ldots;X_t|U) = \sum_i H(X_i|U) - H(X_{[1:t]}|U)$ is Watanabe's total correlation and the minimum is over auxiliary variables with $|U| \le \prod_i |X_i| + t$. For $t=2$ this reduces to $\min_{p(u|x,y)} \max\{I(X;Y|U), I(X,Y;U)\}$, which the paper shows coincides with the fixed point of relaxed Wyner's common information $C_\gamma(X;Y) = \min_{p_{U|XY}: I(X;Y|U) \le \gamma} I(X,Y;U)$; thus relaxed Wyner's common information is not merely an optimization device but the exact communication cost of two-party coordination with private shared randomness. On the converse side, the proof bounds $I(X^n;Y^n|M)$ by the message rate $nR$, showing that the coordinator's message limits how much shared randomness can leak through the outputs. The paper further proves the full simulation rate region in the oblivious-coordinator case: a rate tuple is achievable exactly when $R + R_S \ge I(X_{[1:t]};U,U_S)$ for every $S \subseteq [1:h]$ over product-form distributions, a region that reduces to multi-user Wyner's common information when all shared-randomness rates vanish.

Load-bearing premise

The achievability proofs depend on external random-binning lemmas, namely the Output Statistics of Random Binning framework, holding exactly for the particular binning and Slepian-Wolf decoders used here; if those approximation lemmas fail for these schemes, the single-letter rate formulas are not established.

Editorial extensions

If this is right

When two processors share private randomness and an omniscient coordinator broadcasts, the optimal rate is computable as the fixed point of relaxed Wyner's common information, giving a concrete way to evaluate coordination costs for any finite-alphabet distribution.
Neither pure network coding at rate $C(X;Y)/2$ nor pure channel simulation at rate $I(X;Y)$ is generally optimal; the min-max formula can be strictly smaller than both, as the doubly symmetric binary source example shows.
In the oblivious-coordinator setting, the full trade-off between broadcast rate and shared-randomness rates is known, so a designer can decide how much shared randomness to install to reduce the coordinator's load.
With no shared randomness, the oblivious-coordinator region reduces to multi-user Wyner's common information, so the paper's results extend that classical notion to settings with partial randomness.
When all processors must output the same sequence, exact rate regions are available for both individually shared and randomness-on-the-forehead access structures, and the general structure reduces to a linear trade-off describable by network coding.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The fixed-point reading of the two-processor rate suggests that relaxed Wyner's common information may be the right quantity for other coordination problems where encoders hold private side information, not just the caching context in which it was introduced.
The mixed strategy of splitting shared randomness into a network-coded common part and a private per-processor part is likely the general pattern for optimal coordination; one could test whether the same split appears in minimal schemes for empirical coordination or for more general network topologies.
The oblivious-coordinator rate region is a linear program in the rates once auxiliary variables are fixed, so it can be evaluated numerically; comparing it to the omniscient-coordinator bound on small instances could quantify the value of coordinator access to shared randomness.
The paper leaves open whether the randomness-on-the-forehead upper bound is tight in general; a matching converse for three processors would complete that picture.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague—

Read this one. Kurri, Prabhakaran, Sarwate on coordination through shared randomness. The headline result is Theorem 2: the optimal transmission rate for two processors with individually shared randomness is the fixed point of relaxed Wyner's common information, min max{I(X;Y|U), I(X,Y;U)}. That gives Gastpar-Sula's optimization a concrete operational meaning, which is a real step forward. The multi-processor generalization (Theorem 6) and the full oblivious-coordinator region (Theorem 13) are genuinely new. Theorem 13 recovers the Xu-Liu-Chen multi-user Wyner common information as a special case, which is a nice sanity check.

The paper is careful. The converse arguments use standard single-letterization, and the two-processor converse has a genuinely new bit: bounding I(Xn;Yn|M) through the shared randomness, which is not zero as in Wyner's model. The authors state their open problems honestly—tightness of the forehead bound and the DSBS optimizer conjecture—without overselling Theorem 8. The DSBS example actually shows the upper bound is strict, which is a good faith test.

Soft spots: the achievability proofs lean heavily on OSRB (Yassaee et al.) and several are condensed. Theorem 6's achievability is an outline in Appendix B; Theorem 13's proof outline in Appendix D does not display the full 2^h case analysis. But the two-processor proof in Section III-A shows the structure, and the stress-test checked the second-moment computation for the t=h=3 oblivious case; the exponents do yield exactly the claimed constraints. So this is a completeness issue, not a demonstrated gap. The reliance on OSRB is standard for this subfield, and the invoked theorems are external, not circular. I don't see the circularity burden the reader flagged; the derivations are against independent benchmarks.

If I were refereeing I'd ask for the appendix expansions before publication—especially the negative-rate regularization in the multi-processor OSRB elimination—but I wouldn't block on it. The paper is within its rights to use standard machinery.

Audience: people working on coordination, common information, and channel simulation. It won't reshape adjacent fields, but it resolves an open question and gives an existing quantity meaning. I'd bring it to reading group and I'd cite it. Send it to peer review.

Referee Report

2 major / 4 minor

Summary. The paper studies strong coordination of i.i.d. outputs in a star network where a coordinator sends a common message to processors that also have access to subsets of independent shared-randomness sources. Two settings are considered: the omniscient coordinator, which observes all shared randomness, and the oblivious coordinator, which observes none. The main contributions are a complete characterization of the optimal transmission rate for two processors (Theorem 2), which is shown to equal a fixed point of relaxed Wyner's common information; a characterization for the multi-processor individually shared randomness model in terms of Watanabe's total correlation (Theorem 6); an upper bound for the randomness-on-the-forehead model (Theorem 8); complete rate regions when all outputs are equal (Theorems 7, 9, 10); a characterization for the correlated shared randomness model with identical outputs (Theorem 11); and a complete characterization of the rate region in the oblivious coordinator setting for arbitrary subset structures (Theorems 12 and 13). The proofs use the Output Statistics of Random Binning framework and channel-resolvability-style second-moment analysis.

Significance. If the results are correct, this is a significant contribution to coordination theory. The two-processor result (Theorem 2) gives an operational meaning to relaxed Wyner's common information, and the oblivious-coordinator rate region (Theorem 13) extends multi-user Wyner common information to settings with shared randomness, which is a natural and useful generalization. The paper contains detailed and convincing proofs for the two-processor setting (Theorems 1 and 2) and for the three-processor oblivious case (Theorem 12), and the converse arguments are standard single-letterizations. The DSBS example (Example 1) illustrates, under a stated conjecture, that the optimal rate can be strictly better than both the network-coding-based scheme and the channel-simulation scheme. The authors are explicit about which results are bounds (Theorem 8) and which are complete characterizations. The main weakness is that the proofs of two central multi-processor theorems (Theorems 6 and 13) are presented only as outlines in Appendices B and D, which detracts from the rigor expected for a full characterization; this is a fixable issue rather than a demonstrated error.

major comments (2)

[Section IV-B and Appendix B] The achievability proof of Theorem 6 is given only as an outline. The rate constraints in (159)-(161) are stated without deriving them from the OSRB framework, and the elimination from these constraints to the two inequalities in (163) is not carried out. In addition, the intuitive scheme described in Section IV-B includes a network-coded common-randomness index m0 of rate R0 and a resulting message rate R = (t-1)R0/t + R*, but the formal constraints in Appendix B contain no R0 and conclude R = R*. The paper should explain why R0 can be set to zero (or otherwise justify the reduction). Furthermore, the non-negativity regularization for \hat{R0} when R* > H(U), which is handled for Theorem 1 in Appendix E-B, is not mentioned for the multi-processor case. Since Theorem 6 is a central characterization, the proof should be completed or the omitted steps explicitly identified as routine.
[Appendix D and Theorem 13] The proof of Theorem 13, which claims a complete characterization of the oblivious-coordinator rate region for arbitrary number of processors and arbitrary subset structures, is only an outline. It refers to the second-moment analysis of Theorem 12 but does not display the exponent bounds for the 2^h + 1 cases for general h, the typicality arguments, or the final summation step for arbitrary V_i. Because this theorem is a headline result in the abstract, the authors should either provide a full proof or explicitly present the theorem as a proof sketch and include the detailed derivation in a supplementary document.

minor comments (4)

[Theorem 13 statement] The rate region in Theorem 13 is written for non-negative rate tuples (R,R_1,...,R_t), but the subset condition S ⊆ [1:h] refers to h shared-randomness variables; the tuple should be (R,R_1,...,R_h). This is a notational error that should be corrected.
[Appendix D] In the proof outline of Theorem 13, the target distribution is written as q(x[1t3]) instead of q(x[1:t]); this is a typo.
[Appendix C and Theorem 8] The proof of Theorem 8 is presented only for t = 3, with the statement that a similar proof works for any t. Since Theorem 8 is only an upper bound, this is acceptable, but the paper should at least sketch how the definitions of r_i in (61) arise from the elimination step for general t.
[Section IV-B] The intuitive explanation of the achievability for Theorem 6 uses a rate R = (t-1)R0/t + R*, while the formal outline in Appendix B uses R = R*. The relation between these two descriptions should be clarified to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivations are self-contained achievability and converse arguments against external benchmarks.

full rationale

The paper's central results (Theorems 2 and 6 for the omniscient coordinator, and Theorem 13 for the oblivious coordinator) are obtained by explicit achievability schemes based on the external Output Statistics of Random Binning framework and by single-letter converse bounds derived from the simulation-code definition, not by assuming the claimed rate expressions. The relaxed Wyner common information C_gamma is introduced only in Remark 1 as a post-hoc equivalence: Theorem 2 first derives Ropt = min max{I(X;Y|U), I(X,Y;U)} through the OSRB-based achievability and the converse bounding I(X^n;Y^n|M) <= nR, and only then observes that this equals the fixed point C_gamma* = gamma*. Similarly, Theorem 6 derives the total-correlation expression from a multi-processor generalization of the same converse and an outlined OSRB achievability, with the cardinality bound from the Convex Cover Method. The oblivious coordinator region in Theorem 13 is proved by the second-moment channel-resolvability analysis in Theorem 12 and a converse using n(R+R_S) >= H(W,W_S) >= I(W,W_S;X^n), again without fitting parameters or importing a uniqueness theorem from the authors' prior work. The paper contains no self-citations that carry a load-bearing argument; the cited prior results (Wyner, Cuff, Yassaee et al., Gastpar and Sula, Xu et al.) are external and are either used as standard tools or shown to be recovered as special cases. The only explicitly open items, such as the optimality of p_{t*} for DSBS in Example 1, are stated as conjectures and do not enter the derivations. Hence there is no identifiable circular step: the claimed characterizations are not equivalent by construction to their inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No numerical constants are fitted to data. The auxiliary random variables U and U_i are standard information-theoretic optimization variables, not invented physical entities. The results rely on well-established external theorems from random binning, common information, and network coding.

assumptions (6)

standard math Output Statistics of Random Binning (OSRB) theorem and related lemmas from Yassaee et al. hold and apply to the binning schemes used in Theorems 1, 6, 8, 11, 12, and 13.
Used in Section III-A proof of Theorem 1, equations (11), (18), and (20), and in Appendix B, C, and D; all achievability results inherit this external theorem.
standard math Wyner's common information characterization for the no-common-randomness two-processor problem is correct and extends to the asymptotic setting considered here.
Used in Theorem 4 and as a benchmark; the multi-user generalization of Xu et al. is recovered in Remark 4.
standard math Network coding multicast with receiver side information achieves the rate max_i sum_{j: j not in V_i} r_j for delivering all shared sources to all processors.
Used in the achievability proof of Theorem 10, Section IV-B.3, citing Yeung and Fragouli-Soljanin.
standard math The Convex Cover Method provides the cardinality bounds |U| <= |X||Y|+2 or product+t while preserving the relevant mutual informations and Markov structure.
Used in the converses of Theorem 2, equation (48), and Theorem 6.
domain assumption Finite alphabets, independent and uniform shared random sources, asymptotically vanishing total variation, and private randomization at coordinator and processors define the model.
Problem definition in Section II; all theorems are stated relative to this model.
standard math Channel resolvability results used in the oblivious achievability proofs are valid for the codebook generation here.
Used in the proof of Theorem 12 in Section VI, following Hayashi, Cuff, and Yassaee et al.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coordination Through Shared Randomness." pith.science (2026). https://pith.science/paper/YKPBBYN2

@misc{pith2026190808407,
  author       = {Pith},
  title        = {Pith review of: Coordination Through Shared Randomness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YKPBBYN2}},
  note         = {Machine review of arXiv:1908.08407}
}

read the original abstract

We study a distributed sampling problem where a set of processors want to output (approximately) independent and identically distributed samples from a joint distribution with the help of a common message from a coordinator. Each processor has access to a subset of sources from a set of independent sources of "shared" randomness. We consider two cases -- in the "omniscient coordinator setting", the coordinator has access to all these sources of shared randomness, while in the "oblivious coordinator setting", it has access to none. All processors and the coordinator may privately randomize. In the omniscient coordinator setting, when the subsets at the processors are disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. For the two-processor case, the optimal rate matches a special case of relaxed Wyner's common information proposed by Gastpar and Sula (2019), thereby providing an operational meaning to the latter. We also give an upper bound on the communication rate for the "randomness-on-the-forehead" model where each processor observes all but one source of randomness and we give an achievable strategy for the general case where the processors have access to arbitrary subsets of sources of randomness. Also, we consider a more general model where the processors observe components of correlated sources (with the coordinator observing all the components), where we characterize the communication rate when all the processors wish to output the same random sequence. In the oblivious coordinator setting, we completely characterize the trade-off region between the communication and shared randomness rates for the general case where the processors have access to arbitrary subsets of sources of randomness.

Figures

Figures reproduced from arXiv: 1908.08407 by the authors.

**Figure 2.** Oblivious coordinator setting. Blue, purple, and green colors represent [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** A schematic diagram of the coding scheme for the achievability part [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: A rate of 0.5C(X; Y ) is achievable. (a) The model on the left is the setup for Wyner’s common information problem [2]. The coordinator sends a uniformly distributed common message to both the processors who may output i.i.d. samples from a given joint distribution. Th…

**Figure 5.** Figure 5: A rate of I(X; Y ) is achievable. (a) The model on the left is the setup for the channel simulation problem of Bennett et al. [3] and Winter [4]. An encoder observing i.i.d. Xn sends a message of rate R to decoder to approximate a noisy channel qY |X between them. Comm…

**Figure 6.** Figure 6: In both the plots (t ∗, f(t ∗)) is the minimum point which illustrates that f(t ∗) < min{f(0), f(1)}, where (0, f(0)) and (1, f(1)) are the respective corner points. (Top) Case when f(0) = 0.5C(X; Y ) < I(X; Y ) = f(1). t ∗ = 0.343436 for a = 0.1. (Bottom) Case when f(…

**Figure 7.** Figure 7: Omniscient coordinator with correlated shared randomness model. [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 56 canonical work pages

[1]

Coordination capacity,

P. Cuff, H. Permuter, and T. Cover, “Coordination capacity,” IEEE Transactions on Information Theory , vol. 56, no. 9, pp. 4181–4206, 2010

work page 2010
[2]

The common information of two dependent random variables,

A. Wyner, “The common information of two dependent random variables,” IEEE Transactions on Information Theory , vol. 21, no. 2, pp. 163–179, 1975

work page 1975
[3]

Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,

C. Bennett, P. Shor, J. Smolin, and A. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,” IEEE Transactions on Information Theory , vol. 48, no. 10, pp. 2637–2655, 2002

work page 2002
[4]

Compression of sources of probability distributions and density operators,

A. Winter, “Compression of sources of probability distributions and density operators,” arXiv preprint quant-ph/0208131 , 2002

arXiv 2002
[5]

Distributed channel synthesis,

P. Cuff, “Distributed channel synthesis,” IEEE Transactions on Informa- tion Theory, vol. 59, no. 11, pp. 7071–7096, 2013

work page 2013
[6]

The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,

C. Bennett, I. Devetak, A. Harrow, P. Shor, and A. Winter, “The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,” IEEE Transactions on Information Theory , vol. 60, no. 5, pp. 2926–2959, 2014

work page 2014
[7]

The information- theoretic costs of simulating quantum measurements,

M. Wilde, P. Hayden, F. Buscemi, and M.-H. Hsieh, “The information- theoretic costs of simulating quantum measurements,” Journal of Physics A: Mathematical and Theoretical , vol. 45, no. 45, p. 453001, 2012

work page 2012
[8]

The commu- nication complexity of correlation,

P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan, “The commu- nication complexity of correlation,” IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 438–449, 2010

work page 2010

Show all 57 references

[9]

Secure cascade channel synthesis,

S. Satpathy and P. Cuff, “Secure cascade channel synthesis,” in IEEE International Symposium on Information Theory , 2013, pp. 2955–2959

2013
[11]

On non-interactive simulation of joint distributions,

S. Kamath and V . Anantharam, “On non-interactive simulation of joint distributions,” IEEE Transactions on Information Theory , vol. 62, no. 6, pp. 3419–3435, 2016

2016
[12]

Common randomness and distributed control: A counterexample,

V . Anantharam and V . Borkar, “Common randomness and distributed control: A counterexample,” Systems & Control Letters , vol. 56, no. 7, pp. 568 – 572, 2007

2007
[13]

Exact common information,

G. Kumar, C. Li, and A. El Gamal, “Exact common information,” in 2014 IEEE International Symposium on Information Theory , 2014, pp. 161–165

2014
[14]

Sufﬁcient conditions for the equality of exact and Wyner common information,

B. Vellambi and J. Kliewer, “Sufﬁcient conditions for the equality of exact and Wyner common information,” in 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , 2016, pp. 370–377

2016
[15]

New results on the equality of exact and Wyner common information rates,

——, “New results on the equality of exact and Wyner common information rates,” in 2018 IEEE International Symposium on Information Theory, 2018, pp. 151–155

2018
[16]

Fixed-length strong coordination,

G. Cervia, T. Oechtering, and M. Skoglund, “Fixed-length strong coordination,” in IEEE Information Theory Workshop , 2019

2019
[17]

Empirical processes, typical sequences, and coordinated actions in standard borel spaces,

M. Raginsky, “Empirical processes, typical sequences, and coordinated actions in standard borel spaces,” IEEE Transactions on Information Theory, vol. 59, no. 3, pp. 1288–1301, 2013

2013
[18]

Correlation between channel state and information source with empirical coordination constraint,

M. Le Treust, “Correlation between channel state and information source with empirical coordination constraint,” in IEEE Information Theory Workshop, 2014, pp. 272–276

2014
[19]

Empirical coordination with two-sided state information and correlated source and state,

——, “Empirical coordination with two-sided state information and correlated source and state,” in IEEE International Symposium on Information Theory, 2015, pp. 466–470

2015
[20]

Empirical coordination with channel feedback and strictly causal or causal encoding,

——, “Empirical coordination with channel feedback and strictly causal or causal encoding,” in IEEE International Symposium on Information Theory, 2015, pp. 471–475

2015
[21]

Empirical coordination, state masking and state ampliﬁcation: Core of the decoder’s knowledge,

M. Le Treust and M. Bloch, “Empirical coordination, state masking and state ampliﬁcation: Core of the decoder’s knowledge,” in IEEE International Symposium on Information Theory , 2016, pp. 895–899

2016
[22]

Polar coding for empirical coordination of signals and actions over noisy channels,

G. Cervia, L. Luzzi, M. R. Bloch, and M. Le Treust, “Polar coding for empirical coordination of signals and actions over noisy channels,” in IEEE Information Theory Workshop , 2016, pp. 81–85

2016
[23]

Empirical coordination with multiple descriptions,

M. Mylonakis, P. Stavrou, and M. Skoglund, “Empirical coordination with multiple descriptions,” in Allerton Conference, 2019

2019
[24]

Empirical coordination subject to a ﬁdelity criterion,

——, “Empirical coordination subject to a ﬁdelity criterion,” in IEEE Information Theory Workshop, 2019

2019
[25]

Common information is far less than mutual information,

P. Gacs and J. K ¨orner, “Common information is far less than mutual information,” Problems of Control and Information Theory , vol. 2, 1973

1973
[26]

On sequences of pairs of dependent random variables,

H. Witsenhausen, “On sequences of pairs of dependent random variables,” SIAM Journal on Applied Mathematics , vol. 28, no. 1, pp. 100–113, 1975

1975
[27]

Non- interactive correlation distillation, inhomogeneous Markov chains, and the reverse bonami-beckner inequality,

E. Mossel, R. O’Donnell, O. Regev, J. Steif, and B. Sudakov, “Non- interactive correlation distillation, inhomogeneous Markov chains, and the reverse bonami-beckner inequality,” Israel Journal of Mathematics , vol. 154, pp. 299–336, 2006

2006
[28]

On the (im)possibility of non-interactive correlation distillation,

K. Yang, “On the (im)possibility of non-interactive correlation distillation,” Theor. Comput. Sci., vol. 382, no. 2, pp. 157–166, Aug. 2007

2007
[29]

On extracting common random bits from correlated sources,

A. Bogdanov and E. Mossel, “On extracting common random bits from correlated sources,” IEEE Transactions on Information Theory , vol. 57, no. 10, pp. 6351–6355, 2011

2011
[30]

Common randomness in information theory and cryptography. II. CR capacity,

R. Ahlswede and I. Csisz ´ar, “Common randomness in information theory and cryptography. II. CR capacity,” IEEE Transactions on Information Theory, vol. 44, no. 1, pp. 225–240, 1998

1998
[31]

Common randomness and secret key generation with a helper,

I. Csisz ´ar and P. Narayan, “Common randomness and secret key generation with a helper,” IEEE Transactions on Information Theory , vol. 46, no. 2, pp. 344–366, 2000

2000
[32]

Common randomness in information theory and cryptography. I. secret sharing,

R. Ahlswede and I. Csisz ´ar, “Common randomness in information theory and cryptography. I. secret sharing,” IEEE Transactions on Information Theory, vol. 39, no. 4, pp. 1121–1132, 1993

1993
[33]

Secret key agreement by public discussion from common information,

U. Maurer, “Secret key agreement by public discussion from common information,” IEEE Transactions on Information Theory , vol. 39, no. 3, pp. 733–742, 1993

1993
[34]

Common information and secret key capacity,

H. Tyagi, “Common information and secret key capacity,” IEEE Transactions on Information Theory , vol. 59, no. 9, pp. 5627–5640, 2013

2013
[35]

Secret key generation with one communica- tor and a one-shot converse via hypercontractivity,

J. Liu, P. Cuff, and S. Verd´u, “Secret key generation with one communica- tor and a one-shot converse via hypercontractivity,” in IEEE International Symposium on Information Theory , 2015, pp. 710–714

2015
[36]

On the public communication needed to achieve SK capacity in the multiterminal source model,

M. Mukherjee, N. Kashyap, and Y . Sankarasubramaniam, “On the public communication needed to achieve SK capacity in the multiterminal source model,” IEEE Transactions on Information Theory , vol. 62, no. 7, pp. 3811–3830, 2016

2016
[37]

On the optimality of secret key agreement via omniscience,

C. Chan, M. Mukherjee, N. Kashyap, and Q. Zhou, “On the optimality of secret key agreement via omniscience,”IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2371–2389, 2018

2018
[38]

Privacy ampliﬁcation by public discussion,

C. Bennett, G. Brassard, and J. Robert, “Privacy ampliﬁcation by public discussion,” SIAM Journal on Computing , vol. 17, no. 2, pp. 210–229, 1988

1988
[39]

Generalized privacy ampliﬁcation,

C. Bennett, G. Brassard, C. Crepeau, and U. Maurer, “Generalized privacy ampliﬁcation,” IEEE Transactions on Information Theory , vol. 41, no. 6, pp. 1915–1923, 1995

1915
[40]

Privacy ampliﬁcation secure against active adversaries,

U. Maurer and S. Wolf, “Privacy ampliﬁcation secure against active adversaries,” in Annual International Cryptology Conference . Springer, 1997, pp. 307–321

1997
[41]

Linking information reconciliation and privacy ampliﬁcation,

C. Cachin and U. Maurer, “Linking information reconciliation and privacy ampliﬁcation,” Journal of Cryptology , vol. 10, pp. 97–110, 1997

1997
[42]

Coordination with clustered common randomness in a three-terminal line network,

I. Kadampot and M. Bloch, “Coordination with clustered common randomness in a three-terminal line network,” in IEEE International Symposium on Information Theory , 2017, pp. 1828–1832

2017
[43]

A lossy source coding interpretation of Wyner’s common information,

G. Xu, W. Liu, and B. Chen, “A lossy source coding interpretation of Wyner’s common information,” IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 754–768, 2016

2016
[44]

Information-theoretic caching: Sequential coding for computing,

C. Wang, S. Lim, and M. Gastpar, “Information-theoretic caching: Sequential coding for computing,” IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 6393–6406, 2016

2016
[45]

Relaxed Wyner’s common information,

M. Gastpar and E. Sula, “Relaxed Wyner’s common information,” in IEEE Information Theory Workshop , 2019. 27

2019
[46]

General nonasymptotic and asymptotic formulas in channel resolvability and identiﬁcation capacity and their application to the wiretap channel,

M. Hayashi, “General nonasymptotic and asymptotic formulas in channel resolvability and identiﬁcation capacity and their application to the wiretap channel,” IEEE Transactions on Information Theory , vol. 52, no. 4, pp. 1562–1575, 2006

2006
[47]

Strong coordination over multi-hop line networks using channel resolvability codebooks,

B. Vellambi, J. Kliewer, and M. Bloch, “Strong coordination over multi-hop line networks using channel resolvability codebooks,” IEEE Transactions on Information Theory, vol. 64, no. 2, pp. 1132–1162, 2018

2018
[48]

Information theoretical analysis of multivariate correlation,

S. Watanabe, “Information theoretical analysis of multivariate correlation,” IBM Journal of Research and Development , vol. 4, no. 1, pp. 66–82, 1960

1960
[49]

Linear dependence structure of the entropy space,

T. Han, “Linear dependence structure of the entropy space,” Information and Control, vol. 29, no. 4, pp. 337 – 368, 1975

1975
[50]

Achievability proof via output statistics of random binning,

M. Yassaee, M. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” IEEE Transactions on Information Theory , vol. 60, no. 11, pp. 6760–6786, 2014

2014
[51]

Relaxed Wyner’s common information,

E. Sula and M. Gastpar, “Relaxed Wyner’s common information,” CoRR, vol. abs/1912.07083v1, 2019

1912 arXiv
[52]

El Gamal and Y .-H

A. El Gamal and Y .-H. Kim, Network Information Theory . Cambridge University Press, 2012

2012
[53]

Channel simulation via interactive communications,

M. Yassaee, A. Gohari, and M. Aref, “Channel simulation via interactive communications,” IEEE Transactions on Information Theory , vol. 61, no. 6, pp. 2964–2982, 2015

2015
[54]

Yeung, Information Theory and Network Coding

R. Yeung, Information Theory and Network Coding . Springer Science & Business Media, 2008

2008
[55]

Network coding fundamentals,

C. Fragouli and E. Soljanin, “Network coding fundamentals,”Foundations and Trends in Networking , vol. 2, no. 1, pp. 1–133, 2007

2007
[56]

Computation over multiple-access channels,

B. Nazer and M. Gastpar, “Computation over multiple-access channels,” IEEE Transactions on Information Theory, vol. 53, no. 10, pp. 3498–3516, 2007

2007
[57]

Cover and J

T. Cover and J. Thomas, Elements of Information Theory . Wiley- Interscience, 2006. Gowtham R. Kurri (Member, IEEE) graduated from the International Institute of Information Technology, Hyderabad, India, with a B. Tech. degree in Electronics and Communication Engineering, in 2...

2006
[2014]

His research interests include information theory, machine learning, signal processing, optimization, and privacy and security

He was previously a Research Assistant Professor from 2011 to 2013 with the Toyota Technological Institute at Chicago; prior to this, he was a Postdoctoral Researcher from 2008 to 2011 with the University of California, San Diego, CA. His research interests include information...

2011

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Coordination capacity,

P. Cuff, H. Permuter, and T. Cover, “Coordination capacity,” IEEE Transactions on Information Theory , vol. 56, no. 9, pp. 4181–4206, 2010

work page 2010

[2] [2]

The common information of two dependent random variables,

A. Wyner, “The common information of two dependent random variables,” IEEE Transactions on Information Theory , vol. 21, no. 2, pp. 163–179, 1975

work page 1975

[3] [3]

Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,

C. Bennett, P. Shor, J. Smolin, and A. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,” IEEE Transactions on Information Theory , vol. 48, no. 10, pp. 2637–2655, 2002

work page 2002

[4] [4]

Compression of sources of probability distributions and density operators,

A. Winter, “Compression of sources of probability distributions and density operators,” arXiv preprint quant-ph/0208131 , 2002

arXiv 2002

[5] [5]

Distributed channel synthesis,

P. Cuff, “Distributed channel synthesis,” IEEE Transactions on Informa- tion Theory, vol. 59, no. 11, pp. 7071–7096, 2013

work page 2013

[6] [6]

The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,

C. Bennett, I. Devetak, A. Harrow, P. Shor, and A. Winter, “The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,” IEEE Transactions on Information Theory , vol. 60, no. 5, pp. 2926–2959, 2014

work page 2014

[7] [7]

The information- theoretic costs of simulating quantum measurements,

M. Wilde, P. Hayden, F. Buscemi, and M.-H. Hsieh, “The information- theoretic costs of simulating quantum measurements,” Journal of Physics A: Mathematical and Theoretical , vol. 45, no. 45, p. 453001, 2012

work page 2012

[8] [8]

The commu- nication complexity of correlation,

P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan, “The commu- nication complexity of correlation,” IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 438–449, 2010

work page 2010