{"id":"23f5212f-3f6c-4640-914a-ec3014fc1eda","arxiv_id":"1908.08407","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper characterizes exact communication rates for distributed sampling with shared randomness, giving an operational meaning to relaxed Wyner's common information.","lead":"This paper finds the exact amount of coordination message needed when several processors share random bits and must produce samples from a prescribed joint distribution. The derived formulas link these rates to known information quantities such as Wyner's common information and total correlation.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's verdict of ACCEPT with moderate confidence is well calibrated. The central claims, especially Theorem 6 and Theorem 13, are supported by detailed though partially condensed proofs. The main external dependency is the OSRB framework of Yassaee et al., which is standard in this area and is applied in a way consistent with the t=2 case fully worked out in Theorem 1. I specifically looked for a concrete failure mode in the proof outlines: the omitted negative-rate regularization in Appendix B is a genuine gap in presentation, but the mechanism for handling it is already present in Appendix E-B and extends without changing the rate expression. The oblivious-coordinator achievability proof in Theorem 12 was the other candidate for a hidden error; my case-by-case check of the second-moment bounds shows that the exponents produce exactly the stated inequalities after summing the square roots over the typical set, so the rate region is not missing a constraint. Since no internal inconsistency or unsupported external assumption beyond the acknowledged OSRB reliance was found, the appropriate outcome is to keep the reader's ACCEPT verdict unchanged.","tokens_in":46174,"tokens_out":29527,"duration_ms":269840,"concrete_test":"Fully expand the Appendix B proof of Theorem 6: write the OSRB uniformity conditions for the variables (U,U_1),...,(U,U_t), U, the Slepian-Wolf decoder conditions, and the rate elimination with nonnegative auxiliary rates (using the Appendix E-B regularization when \\hat R0 < 0); verify that the final achievable rate is exactly max{total correlation, I(X_[1:t];U)}. If additional constraints survive the elimination, the Theorem 6 formula would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the central derivations in Sections III-A, IV-B, and VI in good faith and did not find a mathematical error. The weakest point is the one the reader flagged: Theorem 6's achievability is presented as an outline (Appendix B) that invokes OSRB without displaying the full set of subset constraints or the negative-rate regularization needed when \\hat R0 = H(U) - R* becomes negative. However, the t=2 proof in Theorem 1 shows the required structure, and the regularization device in Appendix E-B (adding independent W, W_i to make auxiliary rates nonnegative) carries over directly, so this is a completeness issue rather than a demonstrated flaw. I also checked the second-moment achievability for the oblivious coordinator (Theorem 12) case by case; the exponents in (115)-(124) yield exactly the constraints R + R_S > I(A; U, U_S) after the sqrt/sum step, so no missing constraint appears.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":46267,"tokens_out":33753,"duration_ms":292568,"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":[{"comment":"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.","section":"Section IV-B and Appendix B"},{"comment":"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.","section":"Appendix D and Theorem 13"}],"minor_comments":[{"comment":"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.","section":"Theorem 13 statement"},{"comment":"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.","section":"Appendix D"},{"comment":"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":"Appendix C and Theorem 8"},{"comment":"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.","section":"Section IV-B"}],"recommendation":"major_revision","confidential_remarks":"The paper appears to be technically sound in its main ideas, and the detailed proofs for the two-processor and three-processor cases are convincing. My main concern is that two of the central multi-processor characterizations (Theorems 6 and 13) are supported only by proof outlines. I recommend requiring the authors to expand these proofs into full derivations, or at least to provide a detailed appendix with all the OSRB constraints and the second-moment exponent calculations. Once that is done, the paper would be an accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nRead 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.\n\nThe 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.\n\nSoft 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.\n\nIf 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.\n\nAudience: 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.","headline":"Strong paper: gives relaxed Wyner's common information an operational interpretation and nails the oblivious-coordinator rate region; worth a serious referee.","tokens_in":46825,"tokens_out":1508,"would_cite":true,"duration_ms":15804,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17","94A29"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["strong coordination","shared randomness","Wyner's common information","relaxed Wyner common information","distributed sampling","random binning","channel resolvability","total correlation"],"falsifier":"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.","tokens_in":45957,"feed_emoji":"🎲","tokens_out":8169,"duration_ms":74919,"temperature":0.7,"pith_summary":"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.","feed_headline":"Coordinator broadcast rate equals a min-max of mutual informations","feed_subtitle":"Exact formula for the cost of coordinated sampling also explains relaxed Wyner's common information.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Output Statistics of Random Binning theorem and Slepian-Wolf lemmas used in every achievability proof.","marker":"[50]"},{"why":"Defines Wyner's common information, the baseline problem recovered when no shared randomness is present.","marker":"[2]"},{"why":"Defines relaxed Wyner's common information, whose fixed point the paper identifies as the two-processor optimal rate.","marker":"[45]"},{"why":"Provides channel-synthesis achievability ideas and the single-letter approximation lemma used in the converses.","marker":"[5]"},{"why":"Establishes the multi-user Wyner common information problem, recovered as a special case of the oblivious-coordinator rate region.","marker":"[43]"},{"why":"Introduces Watanabe's total correlation, the multivariate mutual information appearing in the optimal individually-shared-randomness rate.","marker":"[48]"},{"why":"Introduces Han's dual total correlation, the quantity appearing in the randomness-on-the-forehead upper bound.","marker":"[49]"}],"fun_headline_variants":["Coordinated sampling rate is a min-max of mutual informations","Omniscient coordinator cost equals relaxed Wyner's common information","Exact broadcast rate for shared randomness coordination","Min-max formula for coordinator-driven distributed sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Coordinated sampling rate is a min-max of mutual informations","Omniscient coordinator cost equals relaxed Wyner's common information","Exact broadcast rate for shared randomness coordination","Min-max formula for coordinator-driven distributed sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000451,"raw_usage":{"total_tokens":2404,"prompt_tokens":1211,"completion_tokens":1193,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":827,"completion_tokens_details":{"reasoning_tokens":1131}},"tokens_in":827,"tokens_out":1193,"duration_ms":8107,"temperature":1.0,"reasoning_tokens":1131,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:41:19.853191+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Achievability proof via output statistics of random binning,","cited_arxiv_id":null,"evidence_quote":"Supplies the Output Statistics of Random Binning theorem and Slepian-Wolf lemmas used in every achievability proof."},{"cited_title":"The common information of two dependent random variables,","cited_arxiv_id":null,"evidence_quote":"Defines Wyner's common information, the baseline problem recovered when no shared randomness is present."},{"cited_title":"Relaxed Wyner’s common information,","cited_arxiv_id":null,"evidence_quote":"Defines relaxed Wyner's common information, whose fixed point the paper identifies as the two-processor optimal rate."},{"cited_title":"Distributed channel synthesis,","cited_arxiv_id":null,"evidence_quote":"Provides channel-synthesis achievability ideas and the single-letter approximation lemma used in the converses."},{"cited_title":"A lossy source coding interpretation of Wyner’s common information,","cited_arxiv_id":null,"evidence_quote":"Establishes the multi-user Wyner common information problem, recovered as a special case of the oblivious-coordinator rate region."},{"cited_title":"Information theoretical analysis of multivariate correlation,","cited_arxiv_id":null,"evidence_quote":"Introduces Watanabe's total correlation, the multivariate mutual information appearing in the optimal individually-shared-randomness rate."},{"cited_title":"Linear dependence structure of the entropy space,","cited_arxiv_id":null,"evidence_quote":"Introduces Han's dual total correlation, the quantity appearing in the randomness-on-the-forehead upper bound."}],"review_version":1}