{"id":"fa48e251-54b1-4159-aab0-f1cf05fb7184","arxiv_id":"2501.12227","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For strong coordination over a MAC, the paper derives an achievable shared-randomness region with cribbing encoders and a tight characterization without cribbing for deterministic links with conditionally independent sources.","lead":"This paper characterizes how much shared randomness two encoders need to coordinate a decoder's output over a noisy multiple-access channel, including when one encoder can secretly observe the other's transmission. It gives exact limits in a special deterministic-link case and shows that letting encoders cooperate shrinks the randomness required.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's tight characterization is not independently proven: achievability is delegated to [9, Theorem 3] without showing the adaptation to a multi-terminal cribbing-free MAC with side information and conditional independence.","rationale":"We stress-tested the two main theorems. For Theorem 1, we manually performed the Fourier-Motzkin elimination on (9)-(20) and verified that the projection onto (R01,R02) yields exactly the constraints (3a)-(3h); the auxiliary redundant bounds (e.g., R01 ≥ H(U1|U2,W,\\tilde{Y}) - H(U1,U2|X1,X2,W,Y)) are implied by (3d)-(3h). The OSRB proof follows the standard structure and no gap was found. For Theorem 2, the converse in Section VI is internally consistent: step (a) in (25) uses the i.i.d. and conditional independence assumptions correctly, and the auxiliary identifications are valid. The example and Proposition 1 are correct, and the 'cribbing helps' demonstration is legitimate because it compares the exact no-cribbing region with an inner bound. The only substantive weakness is that the achievability part of Theorem 2 is not proved; it is delegated to a point-to-point result [9] with a one-sentence assertion. This is exactly the load-bearing condition for the tight characterization. A referee should demand the adapted proof. Therefore we concur with the CONDITIONAL verdict and recommend no change.","tokens_in":13805,"tokens_out":39735,"duration_ms":321990,"concrete_test":"Provide a complete, self-contained achievability proof for Theorem 2: explicitly define the encoders p(\\tilde{x}1^n|x1^n,k1) and p(\\tilde{x}2^n|x2^n,k2), the decoder p(y^n|k1,k2,w^n,\\tilde{y}^n), and prove that for any distribution satisfying (6) and (5a)-(5c), the total variation distance in (1) tends to 0 as n→∞. In particular, show how the point-to-point scheme of [9, Theorem 3] is extended to the MAC with two encoders and decoder side information, and confirm the rate constraints (5a)-(5c) are exactly the resulting conditions. If any step relies on an additional assumption not present in Theorem 2, the tight characterization claim is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 2 is that (5a)-(5c) exactly characterize the rate region for the cribbing-free case with deterministic links and I(X1;X2|W)=0. The converse proof in Section VI is self-contained and appears sound: the chain inequalities (25)-(26) correctly single-letterize with U1i=(K1,\\tilde{Y}1~i,W~i), U2i=(K2,\\tilde{Y}2~i), and the subset argument for the g(ε) term is valid. However, the achievability half of Theorem 2 is not proved in the paper. The statement 'The achievability largely follows from [9, Theorem 3]' is a handwave. [9] treats point-to-point DMC simulation; adapting it to a two-encoder MAC with decoder side information and the conditional independence factorization requires constructing encoders p(\\tilde{x}1|x1,k1), p(\\tilde{x}2|x2,k2), a decoder p(y|k1,k2,w,\\tilde{y}), and showing the induced distribution meets the target q. No such construction or error analysis is given. If the adaptation fails (e.g., the rate constraints from [9] do not map onto (5a)-(5c) when two encoders are present), Theorem 2 is only an outer bound, not a characterization. This is load-bearing because the paper's contribution and the cribbing-helps example both rely on the exactness of the no-cribbing region.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies strong coordination of two encoders over a discrete memoryless multiple-access channel with decoder side information and pairwise shared randomness at limited rates. In the cribbing configuration, Encoder 1 non-causally sees Encoder 2's channel input; the paper gives an inner bound (Theorem 1) based on the Output Statistics of Random Binning. Without cribbing, for a MAC composed of deterministic links and sources satisfying I(X1;X2|W)=0, it claims an exact rate region in the limit R02->infinity (Theorem 2). The paper then evaluates the regions on a binary example and concludes that cribbing strictly reduces the required channel-input entropy.","tokens_in":14076,"tokens_out":14609,"duration_ms":138667,"significance":"If the theorems are correct, this would be one of the first multi-terminal strong-coordination characterizations over noisy channels with encoder cooperation, and it would quantify when cribbing reduces shared-randomness requirements. The paper's strengths include a structurally standard OSRB achievability argument for Theorem 1, a detailed single-letterized converse for Theorem 2, and an explicit numerical example. The proofs are not parameter-fitted and the claims are falsifiable. However, the achievability direction of Theorem 2 is delegated to an external point-to-point result, and several Fourier-Motzkin eliminations are asserted without display, so the current version is not yet a complete characterization.","major_comments":[{"comment":"Theorem 2 is stated as a characterization, but only the converse is proved in Section VI; the achievability half is dismissed with “The achievability largely follows from [9, Theorem 3], by also accounting for the decoder side information and enforcing the conditional independence...” This is load-bearing because exactness of the no-cribbing region and the cribbing-helps comparison in Section IV depend on it. The manuscript must either provide a self-contained code construction for the two-encoder cribbing-free MAC with decoder side information, or a precise reduction showing that [9, Theorem 3] applies to this multi-terminal setting. Until then, (5a)–(5c) is only an outer bound.","section":"Section III, Theorem 2"},{"comment":"The elimination of (R~1,R~2) from (9)–(10), (12)–(14), (18)–(20) is asserted as “the FME procedure” and the resulting eight inequalities (3a)–(3h) are not derived. Since these inequalities define the claimed achievable region, the FME output should be displayed or supplied in an appendix. Without this, the reader cannot verify that no constraint is missing or incorrectly simplified.","section":"Section V, after Eq. (20)"},{"comment":"The three displayed constraints are said to be the specialization of Theorem 1 to independent sources, a perfect channel, and unlimited shared randomness. Substituting W=empty and Y~=(X~1,X~2) into (3a)–(3c) does not directly yield these expressions, and the derivation is not shown. Because this is the quantitative basis for the claim that cribbing reduces H(X~1) from 2 to 1, please prove the displayed constraints or, alternatively, verify directly that the chosen distributions satisfy (3a)–(3c).","section":"Section IV, after Eq. (7)"}],"minor_comments":[{"comment":"The proof of the second inequality in Theorem 2, H(Y~2|W,T) >= I(U2,Y~2;X2|W,T), is not written out; “follows analogously” is acceptable only if the exact auxiliary variable and the same chain are specified. Please add the derivation or a sentence with the exact substitutions.","section":"Section VI"},{"comment":"The heading contains a typo: “F or” should be “For.”","section":"Section IV, Proposition 1"},{"comment":"The definition of g(epsilon) has an unmatched parenthesis; it should read g(epsilon) = 2*sqrt(epsilon) * ( H(S) + log|S| + log(1/sqrt(epsilon)) ).","section":"Equation (24)"},{"comment":"The cardinality bounds for U1, U2, and T are stated, but the justification is a brief reference to [8] and [18]; please provide enough of the perturbation argument for the reader to see how the bound on |T| is obtained.","section":"Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The missing achievability proof for Theorem 2 is, in my view, repairable and does not necessarily invalidate the claimed result; the rest of the paper (converse and OSRB inner bound) is promising. I would ask for a revised version with the FME steps and the [9] adaptation made explicit before publication. No concerns about citation fairness or novelty surfaced in my reading."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a real and useful extension of strong coordination to noisy MACs with encoder cooperation. Theorem 1 gives an achievable region with cribbing via OSRB; Theorem 2 claims a tight no-cribbing region for deterministic links and conditionally independent sources. The main thing to know is that the tightness of Theorem 2 is not fully established in the paper: achievability is delegated to [9, Theorem 3] and the adaptation to a two-encoder MAC with decoder side information is asserted, not shown. A referee should ask for that proof before signing off.\n\nWhat's good: the converse for Theorem 2 (Section VI) is self-contained and the single-letterization looks sound. The chain inequalities (25)-(26) go through with U1i=(K1,Y~1~i,W~i), U2i=(K2,Y~2~i), and the g(ε) term is handled correctly. The example is concrete and the no-cribbing lower bound is actually proven separately in Appendix A, with an explicit achievability construction (U1=X1, U2=X2). So the cribbing-helps conclusion doesn't hinge on the missing achievability half of Theorem 2; that's a point in the paper's favor that the stress-test note underplays.\n\nSoft spots: the Theorem 2 achievability gap is real and load-bearing for the 'tight characterization' claim, though not for the example. The FME step in Theorem 1 is asserted without display; (3a)-(3h) are complex enough that a referee would want to see the elimination. A minor issue: cardinality bounds for the auxiliaries in Theorem 1 are not discussed.\n\nThe paper is honest, with no signs of circularity or curve-fitting. It's a solid advance for the strong coordination subfield. I'd send it to a serious referee and ask for a complete proof of Theorem 2's achievability (or a rigorous reduction to [9]) and a displayed FME derivation for Theorem 1. If those check out, this is a clean accept; as is, it's a conditional.","headline":"Solid extension of strong coordination to noisy MACs with cribbing, but the tight no-cribbing characterization is not fully proven because achievability is delegated to a point-to-point result; a referee should ask for the details.","tokens_in":14606,"tokens_out":6055,"would_cite":true,"duration_ms":53392,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A24","94A40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives the first strong-coordination rate regions for noisy multi-access channels with encoder cribbing, and proves cribbing strictly reduces the shared randomness needed.","keywords":["strong coordination","multiple-access channel","cribbing encoders","channel simulation","shared randomness","encoder cooperation","rate region","source-channel coding"],"falsifier":"Run the no-cribbing version of Example 1 with $\\tilde X_1$ of entropy less than 2 bits and $\\tilde X_2$ of entropy 1 bit and check whether the output can still be made to approximate $Y=X_1B$ in total variation; Proposition 1 says it cannot, so any successful scheme would refute the Theorem 2 region.","tokens_in":1668,"feed_emoji":"🎲","tokens_out":1819,"duration_ms":87799,"temperature":0.7,"pith_summary":"The paper asks how much pairwise shared randomness two encoders and a decoder need to make a noisy multiple-access channel's output approximate i.i.d. samples of a prescribed joint distribution. It derives an achievable region (Theorem 1) when one encoder may crib, meaning it non-causally observes the other encoder's channel input, using joint source-channel coding. Without cribbing, it proves the region is exactly characterized (Theorem 2) for channels whose output is a pair of deterministic functions of the two inputs and for sources that are conditionally independent given the side information. The central message is that encoder cooperation genuinely saves shared randomness: in the computed example, cribbing lowers one encoder's required input entropy from two bits to one.","feed_headline":"Cribbing another encoder's input cuts coordination randomness","feed_subtitle":"New exact rate regions show a cooperating encoder needs less private randomness over a noisy MAC.","key_machinery":"The load-bearing object is the Output Statistics of Random Binning (OSRB) protocol, a random-binning construction used to prove Theorem 1. The cribbing enters through Encoder 1's conditional distribution $p(u_1,\\tilde x_1|x_1,\\tilde x_2,t)$, which lets its codebook depend on Encoder 2's channel input; a Slepian-Wolf decoder at the receiver recovers both source descriptions, and Fourier-Motzkin elimination of auxiliary binning rates yields the rate constraints. For the converse of Theorem 2, the deterministic-link structure and the conditional independence $p(x_1,x_2,w)=p(w)p(x_1|w)p(x_2|w)$ allow the auxiliary variables to be identified as $U_{1i}=(K_1,\\tilde Y_{1\\sim i},W_{\\sim i})$ and $U_{2i}=(K_2,\\tilde Y_{2\\sim i})$, which decouples the two encoder channels and produces a single-letter outer bound that matches the inner bound.","core_discovery":"The paper claims the first strong-coordination rate regions for noisy multiple-access channels with encoder cooperation. Theorem 1 gives an achievable set of shared-randomness rate pairs $(R_{01}, R_{02})$ for any discrete memoryless MAC when Encoder 1 cribs Encoder 2's channel input, stated as the eight inequalities (3a)-(3h) over a joint distribution of the form (4). Theorem 2 shows that without cribbing, when the channel is composed of deterministic links $\\tilde Y=(f_1(\\tilde X_1), f_2(\\tilde X_2))$ and $I(X_1;X_2|W)=0$, the region with unlimited $R_{02}$ is exactly the three inequalities (5a)-(5c). The paper then works out both regions for a concrete target distribution $Y=X_1B$ and shows cribbing strictly improves the feasible region, reducing the required entropy of $\\tilde X_1$ from 2 bits to 1 bit.","pith_inferences":["The auxiliary-variable identification used in the converse, setting $U_{1i}=(K_1,\\tilde Y_{1\\sim i},W_{\\sim i})$, suggests a general recipe for other networks whose channel output factors across encoders, but this extension is not explored in the paper.","For non-deterministic MACs or sources with $I(X_1;X_2|W)>0$, the gap between Theorem 1's inner bound and any outer bound remains open, so whether cribbing still helps there is untested.","The numerical gain in the example, one bit, equals the entropy of the cribbed source $X_2$, hinting that cribbing may generically save up to $H(X_2)$ bits of encoder-1 randomness, though the paper does not claim this."],"forward_implications":["With cribbing, every rate pair satisfying Theorem 1's eight inequalities is achievable for any finite-alphabet discrete memoryless MAC, giving a computable inner bound for the coordination region.","Without cribbing, under the two structural assumptions, Theorem 2's three inequalities exactly describe the region, meaning no alternative scheme can do better in that setting.","In Example 1, cribbing reduces the required entropy of $\\tilde X_1$ from 2 bits to 1 bit while keeping $\\tilde X_2$ at 1 bit, so encoder cooperation strictly enlarges the feasible set.","The results extend channel simulation from point-to-point links to a three-terminal multi-access setting and bring the classic cribbing model from MAC information theory into strong coordination."],"supporting_citations":[{"why":"Supplies the Output Statistics of Random Binning framework and Lemma 4 used to prove Theorem 1's achievability.","marker":"[15]"},{"why":"Provides the Slepian-Wolf decoding conditions used to recover the two source descriptions at the decoder.","marker":"[16]"},{"why":"Theorem 2's achievability largely follows from its channel-simulation result, adapted to decoder side information and conditional independence.","marker":"[9]"},{"why":"Its Lemma 1 bounds the dependency between coordinates under near-i.i.d. coupling and is used in the converse.","marker":"[17]"},{"why":"Provides the distributed channel synthesis framework and cardinality/continuity arguments used to complete the converse.","marker":"[8]"},{"why":"Defines cribbing encoders for the discrete memoryless MAC, the cooperation model studied here.","marker":"[11]"},{"why":"Gives the point-to-point channel-simulation setting that the paper extends to three terminals.","marker":"[10]"}],"fun_headline_variants":["Cribbing an encoder's input shrinks coordination rates","Exact rate regions for strong coordination with cribbing","Cribbing encoders cuts randomness for coordination over MAC","Cooperation via cribbing tightens strong-coordination bounds","Cribbing reduces required randomness for coordination"],"cache_read_input_tokens":16768,"weakest_assumption_plain":"The exactness of Theorem 2 rests on two structural assumptions, the channel output being a pair of deterministic functions of the two encoder inputs and the sources being conditionally independent given the side information, and on borrowing the achievability proof from a prior channel-simulation result; if any of these fails, the paper's tight region and its cribbing-helps conclusion do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Cribbing an encoder's input shrinks coordination rates","Exact rate regions for strong coordination with cribbing","Cribbing encoders cuts randomness for coordination over MAC","Cooperation via cribbing tightens strong-coordination bounds","Cribbing reduces required randomness for coordination"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000573,"raw_usage":{"total_tokens":2706,"prompt_tokens":944,"completion_tokens":1762,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":1685}},"tokens_in":560,"tokens_out":1762,"duration_ms":16903,"temperature":1.0,"reasoning_tokens":1685,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:22:20.507842+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the no-cribbing version of Example 1 with $\\tilde X_1$ of entropy less than 2 bits and $\\tilde X_2$ of entropy 1 bit and check whether the output can still be made to approximate $Y=X_1B$ in total variation; Proposition 1 says it cannot, so any successful scheme would refute the Theorem 2 region.","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 framework and Lemma 4 used to prove Theorem 1's achievability."},{"cited_title":"Noiseless coding of correlated information sources,","cited_arxiv_id":null,"evidence_quote":"Provides the Slepian-Wolf decoding conditions used to recover the two source descriptions at the decoder."},{"cited_title":"When is it possible to simulate a DMC channel from another?","cited_arxiv_id":null,"evidence_quote":"Theorem 2's achievability largely follows from its channel-simulation result, adapted to decoder side information and conditional independence."},{"cited_title":"Distributed channel synthesis,","cited_arxiv_id":null,"evidence_quote":"Provides the distributed channel synthesis framework and cardinality/continuity arguments used to complete the converse."},{"cited_title":"The discrete memoryless multiple- access channel with cribbing encoders,","cited_arxiv_id":null,"evidence_quote":"Defines cribbing encoders for the discrete memoryless MAC, the cooperation model studied here."},{"cited_title":"Simulation of a channel with another channel,","cited_arxiv_id":null,"evidence_quote":"Gives the point-to-point channel-simulation setting that the paper extends to three terminals."}],"review_version":1}