Pith. sign in

REVIEW 3 major objections 3 minor 26 references

Multishot Capacity of Networks with Restricted Adversaries

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Multishot capacity of restricted-adversary networks depends on whether the adversary can switch edges.

desk verdict Plausible Diamond/Butterfly results, but the D_t and E_t upper bounds rest on a false claim about Hamming-ball code sizes. read the letter →

arxiv 2506.03361 v1 pith:P53NHRZV submitted 2025-06-03 cs.IT math.IT

Giuseppe Cotardo , Gretchen L. Matthews , Alberto Ravagnani , Julia Shapiro This is my paper · ORCID
classification cs.ITmath.IT MSC 94A2494B60
keywords networkcodingadversarialmultishotcapacityrestrictedadversarydecodingDiamondButterflycut-setbound
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 whether an adversarial network whose errors are restricted to a proper subset of edges can carry more information when used several times instead of once. It establishes that the answer is yes when the adversary is frozen to the same vulnerable edges in every round, and no when the adversary may switch edges between rounds. For the Diamond Network and the Butterfly Network, the $i$-shot capacity in the frozen case is $\log_{|A|}(|A|^i - 1)/i$, which grows toward $1$, while the switching case keeps the one-shot value $\log_{|A|}(|A| - 1)$. These exact formulas, together with a multishot cut-set bound reducing three-level networks to two-level ones, map out which networks benefit from repeated use and which do not.

What carries the argument

The central objects are the $i$-fold product channel $\Omega^i$, built from $i$ independent uses of a network, and the notion of an unambiguous code: a set of messages whose worst-case output sets at every terminal are pairwise disjoint. Against this backdrop, the paper analyzes two adversary models, A.1 and A.2, and shows that the A.1/A.2 distinction controls whether the reserved-vector strategy from one-shot network decoding can be repeated across rounds. A multishot Double Cut-Set Bound then reduces a three-level network to an associated two-level network, which is how the Butterfly Network's capacity is obtained from the Diamond Network's.

What would settle it

Check the true size of the largest unambiguous code for the product channel $H_{D_t}^i$ under the blockwise distance rule stated in Remark 4.7. If, for some $t \ge 2$ and a large alphabet, a code with more than $|A|^i$ blocks exists, then the upper bound in Proposition 4.8 fails and the claimed capacity for $D_t$ is too high.

Watch

Extended reading notes

Core claim

The paper's central claim is that the multishot capacity of a network with a restricted adversary is controlled by whether the adversary can change the attacked edges between uses. In Scenario A.1, where the adversary must keep attacking the same vulnerable edges, the Diamond Network $\mathcal{D}$ and the Butterfly Network $\mathcal{B}$ have $i$-shot capacity $\log_{|A|}(|A|^i - 1)/i$; in Scenario A.2, where the adversary may switch edges each round, the capacity stays at the one-shot value $\log_{|A|}(|A| - 1)$. The Mirrored Diamond Network $\mathcal{S}$ and the families $C_t$ and $D_t$ have capacity $1$ in both scenarios, while family $E_t$ gains in Scenario A.1 and not in Scenario A.2. The paper also extends the Double Cut-Set Bound to repeated uses, which is the step that lets the Butterfly Network's capacity be derived from the Diamond Network's.

Load-bearing premise

The upper bounds for the $C_t$, $D_t$, and $E_t$ families rest on structural remarks (4.5, 4.7, 4.10) stating that the largest unambiguous code on the repeated channel has exactly $|A|^i$ blocks, but those remarks are sketches; the $D_t$ version uses a $3t$-distance condition that appears inconsistent with the Hamming-ball channel actually defined there.

Editorial extensions

If this is right

  • Used repeatedly with a frozen adversary, the Diamond Network, Butterfly Network, and family $E_t$ achieve a strict capacity gain over one shot, with the gain disappearing when the adversary may switch edges.
  • The Mirrored Diamond Network and families $C_t$ and $D_t$ have the same capacity in the one-shot and multishot regimes in both scenarios, so repeated use gives no throughput benefit there.
  • The multishot Double Cut-Set Bound lets the capacity of a three-level network be bounded by that of an associated two-level network, which is how the Butterfly Network's exact capacity follows from the Diamond Network's.
  • For families $A_t$ and $B_s$, a capacity-achieving one-shot strategy would imply a multishot lower bound in the frozen-adversary scenario, indicating a gain once those one-shot capacities are settled.

Reading between the lines

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

  • The freeze-versus-switch dichotomy probably applies beyond the networks studied here: any restricted-adversary network whose one-shot code reserves a fixed set of symbols for adversarial detection should show the same pattern, with the reserved set becoming a reserved vector over repeated rounds.
  • A natural next test, left open by the paper, is letting the vulnerable edge set itself change between rounds; the multishot capacity would likely interpolate between the frozen and switching values depending on how many vulnerable sets the adversary may choose.
  • If the structural lemmas behind the $C_t$, $D_t$, and $E_t$ upper bounds are repaired, the same blockwise-distance method could yield exact multishot capacities for general two-level networks whose one-shot capacity is still unknown; if they are not repaired, the proven part of the theory reduces to the Diamond and Butterfly cases.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper investigates the i-shot capacity of networks with restricted adversaries, considering two adversarial models: the adversary is frozen to the same vulnerable edge set across uses (Scenario A.1) or may switch edges between uses (Scenario A.2). The main results are capacity formulas for the Diamond Network, the Mirrored Diamond Network, families C_t, D_t, E_t, and the Butterfly Network, together with a multishot double cut-set bound and a reduction from 3-level to 2-level networks. The lower-bound constructions are explicit and the Butterfly/Diamond contrast is the paper's strongest conceptual contribution. However, the upper-bound proofs for the family results in Section 4.2 rely on structural lemmas about unambiguous codes for product Hamming channels that are only sketched and, in the cases of D_t and E_t, are not correct as stated.

Significance. The question addressed—whether multiple uses of a network can increase capacity when the adversary is restricted to a vulnerable region—is natural and has not been previously studied. The Scenario A.1/A.2 contrast is conceptually interesting, and the Butterfly Network results (Propositions 5.6 and 5.7) provide a concrete, checkable instance where freezing the adversary's edge set yields a strict multishot gain. The multishot cut-set bound framework in Section 5 is a useful structural tool. However, the paper's advertised computation of the family capacities in Table 2 is not presently supported: the upper-bound machinery in Section 4.2 depends on structural claims that are false or inadequately proved. If the authors can supply correct proofs for the C_t, D_t, and E_t upper bounds, the paper would be a solid contribution; as it stands, only the Diamond, Mirrored Diamond, and Butterfly results are fully established.

major comments (3)
  1. [§4.2.2, Remark 4.7 and Proposition 4.8] The claim that H_Dt : A^{4t} -> A^{4t}, H_Dt(x) = {y : d_H(x,y) ≤ t}, has largest unambiguous code of size |A| is false. An unambiguous code for this channel is exactly a q-ary code of length 4t and minimum Hamming distance at least 2t+1, and the Singleton bound gives size at least |A|^{2t} for sufficiently large alphabets (e.g., |A|=16, t=2 gives 16^4 codewords). The subsequent 'if and only if' condition using block distance 3t is also incorrect: for the i-fold channel unambiguity requires some block to have distance at least 2t+1, not 3t. Since Proposition 4.8's upper bound relies on Remark 4.7, the result C_i(D_t)=1 and the D_t row of Table 2 are unsupported.
  2. [§4.2.3, Remark 4.10 and Proposition 4.11] The same defect appears for E_t. H_Et is a Hamming ball of radius t in A^{2t+1}, so the largest unambiguous code for H_Et has size |A| (attained by the repetition code), not |A|-b. The reserved-vector set B of size b is a property of the network code used in the one-shot construction, not of the abstract channel H_Et. Consequently the claimed upper bound |C| ≤ (|A|-b)^i for codes unambiguous for H^i_Et is false in general; for example the product repetition construction gives |C| = |A|^i. Proposition 4.11's Scenario A.2 capacity is therefore not established, and Remark 4.12 inherits the problem.
  3. [§4.2.1, Remark 4.5 and Proposition 4.6] The structural lemma for C_t is also not proved correctly. The sketch asserts that after forcing some initial coincidence, the remaining codewords must have Hamming weight 2t+1 and that any two such vectors have Hamming distance at most t+1; this is false, since two weight-(2t+1) vectors in A^{2t+1} can have distance 2t+1. The argument also claims that a three-word code of minimum distance 2t+1 contradicts C_1(H_Ct)=1, but for |A| ≥ 3 the repetition code already gives three such codewords. Since Proposition 4.6's upper bound depends on Remark 4.5, the C_t result currently lacks a valid proof; a complete and correct proof is needed.
minor comments (3)
  1. [§5.1, Proposition 5.6 proof] There is a typo in the sentence introducing the network code F: 'LetFwhereV1,V2,V3 andV4 proceed as follows: ff' should read 'Let F where V1, V2, V3 and V4 proceed as follows:'.
  2. [§4.2.3, Remark 4.10] The text refers to 'H_i_C' and 'H_C' in the last two sentences; these should be 'H^i_Et' and 'H_Et' respectively.
  3. [§4.2.2, Proposition 4.8 discussion] The sentence 'Thus, we have that C_i(Ct) = C_i(Dt) = 1 in Scenario A.2' attributes an A.2 result to C_t that Proposition 4.6 does not explicitly prove; the argument that the proof is scenario-independent should be spelled out for C_t.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the multishot capacities are derived from explicit product-channel models and cited published predecessor results, not from fitted inputs.

full rationale

None of the claimed multishot capacities reduces to its own inputs by construction. The Diamond and Mirrored Diamond capacities in Section 4.1 are explicitly attributed to the authors' earlier [7] ("In [7, Section III], we compute the i-shot capacity of D"); the Butterfly upper bound in Propositions 5.6/5.7 then combines that published value with the newly proved multishot double cut-set bound of Theorem 5.3, and the lower-bound codes are new constructions rather than restatements of the capacities. The parameter b in (4.1) is defined as the shortfall of the largest one-shot E_t code from |A| and carried through as an unknown; this is a legitimate parametrization, not a fitted datum renamed a prediction. The unproved "we claim" structural assertions in Remarks 4.5, 4.7, and 4.10 (and the apparent inconsistency in Remark 4.7 between the Hamming-ball definition of H_Dt and the 3t-distance condition) are correctness or missing-proof risks for Propositions 4.6, 4.8, and 4.11, but a false or omitted lemma is not the same as a circular derivation. The cited results [2], [7], and [14] are prior published theorems with their own proofs, so the overlapping authorship of [2] and [7] does not make the argument circular.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central results rest on standard zero-error capacity facts, the reduction machinery of [2], and, for the family upper bounds, unproved structural lemmas stated as Remarks. The free parameter b appears in the E_t and general lower-bound formulas and is not evaluated in the paper. No new physical or information-theoretic entities are postulated.

free parameters (1)
  • b = unspecified; |B| with C_1(E_t)=log_{|A|}(|A|-b)
    The multishot capacity formulas for E_t, Propositions 4.9 and 4.11, and the general lower bound, Lemma 5.8, are stated in terms of b, the number of reserved vectors, which is inherited from the one-shot capacity and not computed in this paper.
assumptions (3)
  • standard math The zero-error capacity of the i-fold product of a channel is additive, C_1(Omega^i) = i C_1(Omega) for product channels, invoked via [14, Prop. 12] for lower bounds.
    Used in lower-bound arguments for C_t, D_t, E_t, and Butterfly; standard in zero-error information theory but not proved in the paper.
  • ad hoc to paper The structural upper-bound lemmas in Remarks 4.5, 4.7, and 4.10: an unambiguous code for H^i_Ct, H^i_Dt, or H^i_Et has size at most |A|^i, with the block-distance conditions 2t+1, 3t, and 2t+1 respectively.
    These remarks are sketches, using 'we claim' and references to [2, Example 9] and [14, Example 9], and they carry the upper-bound proofs of Propositions 4.6, 4.8, and 4.11.
  • domain assumption The fan-out equality between a simple 3-level network and its reduced 2-level network persists for the i-th power channel, Proposition 5.1, extending [2, Theorem 5.8].
    This is the mechanism behind Corollary 5.5 and the Butterfly capacity computation; it is argued by checking definitions but relies on the reduction construction from [2].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multishot Capacity of Networks with Restricted Adversaries." pith.science (2026). https://pith.science/paper/P53NHRZV

@misc{pith2026250603361,
  author       = {Pith},
  title        = {Pith review of: Multishot Capacity of Networks with Restricted Adversaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P53NHRZV}},
  note         = {Machine review of arXiv:2506.03361}
}
read the original abstract

We investigate adversarial network coding and decoding, focusing on the multishot regime and when the adversary is restricted to operate on a vulnerable region of the network. Errors can occur on a proper subset of the network edges and are modeled via an adversarial channel. The paper contains both bounds and capacity-achieving schemes for the Diamond Network, the Mirrored Diamond Network, and generalizations of these networks. We also initiate the study of the capacity of 3-level networks in the multishot setting by computing the multishot capacity of the Butterfly Network, considered in [IEEE Transactions on Information Theory, vol. 69, no. 6, 2023], which is a variant of the network introduced by Ahlswede, Cai, Li and Yeung in 2000.

Figures

Figures reproduced from arXiv: 2506.03361 by the authors.

Figure 1
Figure 1. The Butterfly Network B. i-shot capacity of B shown in Theorem 5.6 is log|A | (|A | i − 1) i . In this restricted adversarial model, there is a gain in using B multiple times for communication. In contrast, when the adversary is free to change the edges attacked each transmission round, we show in Theorem 5.7, that the i-shot capacity of B is log|A | (|A | − 1), the same as the one-shot capacity. When the adversary … view at source ↗
Figure 2
Figure 2. The Diamond Network D. S V1 V2 T e1 e2 e3 e4 e4 e5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The Mirrored Diamond Network S . Theorem 3.6 (Singleton Cut-Set Bound [14, Corollary 66]). Let t ≥ 0 and let A be an alphabet. Suppose that an adversary AN can corrupt up to t edges from a subset U ⊆ E . We have that C1(N , A , AN ) ≤ min T ∈T min E ′ [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [7]

    Cotardo, G

    G. Cotardo, G. Matthews, A. Ravagnani and J. Shapiro. Multishot adversarial net- work decoding,2023 59th Annual Allerton Conference on Communication, Control, and Computing, pp 1–8, 2023

    work page 2023

  2. [1]

    Ahlswede, N

    R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network information flow,IEEE Transac- tions on Information Theory, vol. 46, no. 4, pp. 1204–1216, 2000

    work page 2000

  3. [2]

    Beemer, A

    A. Beemer, A. Kıli¸ c, and A. Ravagnani. Network decoding,IEEE Transactions On Information Theory, vol. 69, no. 6, pp. pp.3708–3730, 2023

    work page 2023

  4. [3]

    Beemer, A

    A. Beemer, A. Kıli¸ c, and A. Ravagnani. Network decoding against restricted adver- saries,IF AC-PapersOnLine, vol. 55, pp. 236–241, 2022

    work page 2022

  5. [4]

    The Curious Case of the Diamond Network

    A. Beemer and A. Ravagnani. The curious case of the diamond network,arXiv preprintarXiv:2107.02144, 2021

    work page Pith review arXiv 2021

  6. [5]

    Cai and R

    N. Cai and R. Yeung. Network error correction, I: Basic concepts and upper bounds, Communications in Information and Systems, vol. 6, pp. 19–36, 2006

    work page 2006

  7. [6]

    Cai and R

    N. Cai and R. Yeung. Network error correction, II: Lower bounds,Communications in Information and Systems, vol. 6, no. 1, pp. 37–54, 2006. 21

    work page 2006

  8. [8]

    T. K. Dikaliotis, T. Ho, S. Jaggi, S. Vyetrenko, H. Yao, M. Effros, J. Kliewer, and E. Erez. Multiple-access network information-flow and correction codes.IEEE Transac- tions on Information Theory, vol. 57, no. 2, pp. 1067–1079, 2011

    work page 2011

Show all 26 references
  1. [9]

    Jaggi, M

    S. Jaggi, M. Langberg, T. Ho, and M. Effros. Correction of adversarial errors in networks,Proceedings International Symposium on Information Theory, 2005, ISIT 2005, Adelaide, SA, Australia, 2005, pp. 1455–1459, 2005

    2005

  2. [10]

    Jaggi, M

    S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. M´ edard. Resilient network coding in the presence of byzantine adversaries,”IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, Anchorage, AK, USA, pp. 616–624, 2007

    2007

  3. [11]

    K¨ oetter and F

    R. K¨ oetter and F. Kschischang. Coding for errors and erasures in random network coding,IEEE Transactions on Information theory, vol. 54, no.8, pp. 3579–3591, 2008

    2008

  4. [12]

    K¨ otter and M

    R. K¨ otter and M. M´ edard. An algebraic approach to network coding,IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782–795, 2003

    2003

  5. [13]

    S. Kurz. Capacity of an infinite family of networks related to the diamond network for fixed alphabet sizes,Designs, Codes and Cryptography, pp. 1–13, 2024

    2024

  6. [14]

    Kschichang and A

    F. Kschichang and A. Ravagnani. Adversarial network coding,IEEE Transactions on Information Theory, vol. 65, pp. 198–219, 2018

    2018

  7. [15]

    S. Li, R. Yeung, and N. Cai. Linear network coding,IEEE Transactions on Informa- tion Theory, vol. 49, pp. 371–381, 2003

    2003

  8. [16]

    Mart´ nez-Pe˜ nas and F

    U. Mart´ nez-Pe˜ nas and F. Kschischang. Reliable and secure multishot network coding using linearized Reed-Solomon codes,IEEE Transactions on Information Theory, vol. 65, no. 8, pp. 4785–4803, 2019

    2019

  9. [17]

    Mohajer, M

    S. Mohajer, M. Jafari, S. N. Diggavi, and C. Fragouli. On the capacity of multi- source non-coherent network coding,2009 IEEE Information Theory Workshop on Networking and Information Theory, Volos, Greece, pp. 130–134, 2009

    2009

  10. [18]

    R. W. N´ obrega and B. F. Uchˆ oa-Filho. Multishot codes for network coding: Bounds and a multilevel construction,2009 IEEE International Symposium on Information Theory, Seoul, Korea (South), pp. 428–432, 2009

    2009

  11. [19]

    R. W. N´ obrega, and B. F. Uchˆ oa-Filho. Multishot codes for network coding using rank-metric codes,2010 Third IEEE International Workshop on Wireless Network Coding, pp. 1–6, 2010

    2010

  12. [20]

    Nutman and M

    L. Nutman and M. Langberg. Adversarial models and resilient schemes for network coding,2008 IEEE International Symposium on Information Theory, Toronto, ON, Canada, pp. 171–175, 2008

    2008

  13. [21]

    Silva, F

    D. Silva, F. R. Kschischang, and R. K¨ oetter. A rank-metric approach to error control in random network coding,IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 3951–3967, 2008. 22

    2008

  14. [22]

    C. Shannon. The zero error capacity of a noisy channel,IRE Transactions on Infor- mation Theory, vol. 2, pp. 8–19, 1956

    1956

  15. [23]

    D. Wang, D. Silva, and F. Kschischang. Constricting the adversary: A broadcast transformation for network coding,45th Annual Allerton Conference on Commu- nunications, Control and Computing, 2007

    2007

  16. [24]

    S. Yang, C. Ngai, and R. Yeung. Construction of linear network codes that achieve a refined singleton bound,2007 IEEE International Symposium on Information Theory, Nice, France, pp. 1576–1580, 2007

    2007

  17. [25]

    Yang and R

    S. Yang and R. Yeung. Refined coding bounds for network error correction,IEEE International Symposium on Information Theory, pp. 1–5, 2007

    2007

  18. [26]

    Z. Zhang. Linear network error correction codes in packet networks,IEEE Transac- tions on Information Theory, vol. 54, no. 1, pp. 209–218, 2008. A Some proofs In this section, we provide some background for the convenience of the reader. We start with a definition and proposit...

    2008

Pith tools

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