Adversarial Network Coding
Alberto Ravagnani∗ and Frank R. Kschischang

arXiv:1706.05468v1 [] 17 Jun 2017

The Edward S. Rogers Sr. Department of Electrical and Computer Engineering
University of Toronto, Toronto, ON M5S 3G4, Canada
Email: {ravagnani,frank}@ece.utoronto.ca.

Abstract
A combinatorial framework for adversarial network coding is presented. Channels are described
by specifying the possible actions that one or more (possibly coordinated) adversaries may take.
Upper bounds on three notions of capacity—the one-shot capacity, the zero-error capacity, and
the compound zero-error capacity—are obtained for point-to-point channels, and generalized to
corresponding capacity regions appropriate for multi-source networks. A key result of this paper is
a general method by which bounds on these capacities in point-to-point channels may be ported to
networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple
adversaries acting on specific network edges. Capacity-achieving coding schemes are described for
some of the considered adversarial models.

1

Introduction

In this paper, we propose a mathematical framework for adversarial network coding, introducing
combinatorial tools and techniques for the analysis of communication networks under adversarial
models. The actions that one or more adversaries may take are described using fan-out sets, thereby
allowing for a wide variety of possible communication scenarios. The framework applies to single
and multi-source networks, and to single and multiple adversaries of various kinds. Three notions of
capacity, called “one-shot”, “zero-error”, and “compound zero-error” are defined. For networks, we
study three corresponding notions of capacity region, establishing bounds and describing capacityachieving schemes.
Since 2002, the problem of correcting errors caused by an adversary in the context of network
coding has been an active research area. The fundamentals of error correction within network coding
schemes were originally investigated in [1,2] by Cai and Yeung, who studied errors and erasures in the
framework of single-source networks, and established the network analogues of the Singleton and the
Hamming bounds. Other bounds were derived in [2] for regular networks [2, Definition 4]. Bounds
and error-correcting code constructions also appeared in [1, 3–8].
Various adversarial models have been investigated in the context of network coding. For example,
Byzantine attacks are studied in [9] and [10], in which omniscient adversaries, secret-sharing models,
and adversaries of limited eavesdropping power are considered. Adversaries who can control some of
the network’s vertices are investigated in [11, 12]. End-to-end approaches to error control in random
and coherent network coding were proposed in [13–15], along with efficient coding and decoding
∗

The author was partially supported by the Swiss National Science Foundation through grant n. P2NEP2 168527.

1

schemes based on rank-metric and subspace codes. Other models were proposed in [16–18]. Adversaries
controlling a channel state within probabilistic channel models were studied in [19].
Fan-out set descriptions of adversaries in point-to-point channels were proposed in [15, Section III],
investigating connections between such descriptions and the concept of correction capability of a code.
The problem of error correction in the context of multi-source random linear network coding was
recently addressed in [20–23], and capacity-achieving schemes were given in [23].
Although a wide variety of network adversarial models have been studied by various authors
(mainly focusing on single-source linear network coding), a unified combinatorial treatment of adversarial network channels seems to be absent. One of the goals of this paper is to fill this gap. In
particular, this paper makes the following contributions.
Whereas noisy channels are described within a theory of “probability,” adversarial channels are
described within a theory of “possibility.” Accordingly, throughout this paper, we take a combinatorial
approach to defining and studying channels, rather than a probabilistic one. This approach is inspired
by Shannon’s work [24] on the zero-error capacity of a channel, and motivated by the fact that a
network adversary may not be specified in general via random variables and probability distributions.
In Section 2 we define codes, one-shot capacity, channel products, and the zero-error capacity of a
channel, and we describe how this approach relates to Shannon’s work. In Section 3, we define two
fundamental channel operations: “concatenation” and “union,” and we establish their main algebraic
properties. We also show how they relate to each other and to the notions of capacity.
In Section 4 we study certain adversarial channels called “Hamming-type channels,” whose input
alphabet is a cartesian product of the form As . We consider multiple adversaries who can corrupt or
erase the components of an element x P As , according to certain restrictions, and explicitly compute
the one-shot capacity, the zero-error capacity and the compound zero-error capacity of these channels
(see Subsection 4.2 for the definitions). This extends a number of classical results in Coding Theory.
The study of networks starts with Section 5. In contrast to previous approaches (e.g., [1, 2]), our
framework allows for multi-source networks with a wide variety of adversarial models. We propose
three notions of capacity region of a multi-source adversarial network, which we call the “one-shot
capacity region”, the “zero-error capacity region”, and the “compound zero-error capacity region” (see
Subsection 5.4 for precise definitions). Most previous work in adversarial network coding implicitly
focus on one-shot models (cf. also Remark 5.4.5), while to our best knowledge zero-error and compound
zero-error adversarial models have not so far been investigated.
The centerpiece of this paper is Section 6, in which we show that any upper bounds for the capacities
of Hamming-type channels can be ported to the networking context in a systematic manner. Using
the channel operations defined in Section 3, we show that this “porting technique” applies to all three
notions of capacity region mentioned above, in the general context of multi-source networks. Moreover,
this method does not require the underlying network to be regular, in the sense of [2, Definition 4].
These theoretical results are then applied to concrete networking contexts in Section 7, where
we study multiple adversaries, each with possibly different error and erasure powers, having access
to prescribed subsets of the network edges. The adversaries are in principle allowed to coordinate
with each other. We derive upper bounds for the three capacity regions of such adversarial networks,
extending certain results of [2] to multiple adversaries (restricted or not) and multi-source networks.
In Section 8, we give capacity-achieving schemes for some of the adversarial scenarios investigated
in Section 7. Incorporating ideas from [23] and [25], we show that linear network coding suffices to
achieve any integer point of the capacity regions associated with some simple adversaries. We then
adapt these communication schemes to compound models. Finally, we show that for some adversarial
networks capacity cannot be achieved with linear network coding.
Other classes of adversaries (such as rank-metric adversaries and multiple adversaries having access
to overlapping sets of the network edges) are briefly discussed in Section 9. Finally, Section 10 is
devoted to conclusions and a discussion of open problems.
2

2

Adversarial Channels

In this section we define and study point-to-point adversarial channels, one-shot codes, and one-shot
capacity. We then describe the channel product construction, and define the zero-error capacity of an
adversarial channel, as proposed by Shannon in [24]. Although most of this material is well known,
this section serves to establish notation that will be used throughout the paper.

2.1

Channels, Codes, Capacity

An adversarial channel is described by an input alphabet X , an output alphabet Y, and a collection
tΩpxq : x P X u of subsets of Y, one for each x P X . The set Ωpxq Ď Y is interpreted as the fan-out
set of x, i.e., the set of all symbols y P Y that the adversary can cause to be received when the input
symbol x P X is transmitted. This motivates the following definition.
Definition 2.1.1. An (adversarial) channel is a map Ω : X Ñ 2Y ztHu, where X and Y are finite
non-empty sets called input and output alphabet, respectively. We denote such an adversarial
channel by Ω : X 99KY, and say that Ω is deterministic if |Ωpxq| “ 1 for all x P X . A deterministic
channel can be identified naturally with the function X Ñ Y that associates to x P X the unique
element y P Ωpxq.
In this paper we will restrict our attention to channels whose input and output alphabets are finite.
Definition 2.1.2. Let Ω : X 99K Y be a channel. A (one-shot) code for Ω is a non-empty subset
C Ď X . We say that C is good for Ω when Ωpxq X Ωpx1 q “ H for all x, x1 P C with x ‰ x1 .
In words, a good code for a channel Ω : X 99K Y is a selection of input symbols from X whose
fan-out sets are pairwise disjoint. If channel inputs are restricted to a good code, it is impossible for
an adversary to cause confusion at the receiver about the transmitted symbol.
Definition 2.1.3. The (one-shot) capacity of a channel Ω : X 99K Y is the base-2 logarithm of the
largest cardinality of a good code for Ω, i.e.,
C1 pΩq :“ maxtlog2 |C| : C Ď X is good for Ωu.
Clearly, the capacity of any channel Ω : X 99K Y satisfies 0 ď C1 pΩq ď mintlog2 |X |, log 2 |Y|u.
Example 2.1.4. Let X , Y be finite non-empty sets with Y Ě X . The identity channel Id : X 99K Y
is defined by Ωpxq :“ txu for all x P X . We have C1 pIdq “ log2 |X |.
Example 2.1.5. Let X :“ F42 . Consider an adversary who is capable of corrupting at most one of
the components of any x P F42 . The action of the adversary is described by the channel H : F42 99K F42
defined by Hpxq :“ ty P F42 : dH px, yq ď 1u for all x P F42 , where dH is the Hamming distance. The
code C “ tp0000q, p1111qu is good for H, and there is no good code with larger cardinality. Therefore
we have C1 pHq “ 1.
Channels with the same input and output alphabets can be compared as follows.
Definition 2.1.6. Let Ω1 , Ω2 : X 99K Y be channels. We say that Ω1 is finer than Ω2 (in symbols,
Ω1 ď Ω2 or Ω2 ě Ω1 ) when Ω1 pxq Ď Ω2 pxq for all x P X .
If Ω1 ď Ω2 , then every code that is good for Ω2 is good for Ω1 as well. Therefore we have
C1 pΩ1 q ě C1 pΩ2 q.

3

2.2

Products of Channels

Adversarial channels Ω1 and Ω2 can be naturally combined with each other via a product construction,
giving rise to a third channel denoted by Ω1 ˆ Ω2 .
Definition 2.2.1. The product of channels Ω1 : X1 99K Y1 and Ω2 : X2 99K Y2 is the channel
Ω1 ˆ Ω2 : X1 ˆ X2 99K Y1 ˆ Y2 defined by
pΩ1 ˆ Ω2 qpx1 , x2 q :“ Ω1 px1 q ˆ Ω2 px2 q, for all px1 , x2 q P X1 ˆ X2 .
The following result shows two important properties of the channel product.
Proposition 2.2.2. Let Ω1 , Ω2 , Ω3 be channels. Then
1. pΩ1 ˆ Ω2 q ˆ Ω3 “ Ω1 ˆ pΩ2 ˆ Ω3 q,

2. C1 pΩ1 ˆ Ω2 q ě C1 pΩ1 q ` C1 pΩ2 q.

Proof. The first property is straightforward. To see the second, observe that if C1 and C2 are good
codes for Ω1 and Ω2 (respectively), then C1 ˆ C2 is good for Ω1 ˆ Ω2 .
The associativity of the channel product (part 1 of Proposition 2.2.2) allows expressions such as
Ω1 ˆ Ω2 ˆ Ω3 to be written without danger of ambiguity.
Definition 2.2.3. Let n ě 1 be an integer. The n-th power of a channel Ω : X 99K Y is the channel
Ωn :“ Ω
ˆ ¨ ¨ ¨ ˆ Ω : X n 99K Y n .
looooomooooon
n times

The n-th power of Ω : X 99K Y models n uses of Ω. Recall that the elements of Ωpxq represent
the outputs that an adversary can produce from the input x P X . If the channel Ω is used n times,
then we have Ωn px1 , ..., xn q “ Ωpx1 q ˆ ¨ ¨ ¨ ˆ Ωpxn q.
Remark 2.2.4. In general, the lower bound of part 2 of Proposition 2.2.2 is not tight, i.e., the capacity
of the product channel Ω1 ˆ Ω2 can be strictly larger than the sum of the capacities of the channels
Ω1 and Ω2 . The following example, which will be used repeatedly in the paper, illustrates this point.
Example 2.2.5. Let H : F42 99K F42 be the channel of Example 2.1.5, which has capacity C1 pHq “ 1.
The code C :“ tp00000000q, p00011101q, p10100111q, p11010110q, p11101000qu Ď F42 ˆ F42 is good for the
product channel H ˆ H. Therefore C1 pH ˆ Hq ě log2 p5q ą 2 “ C1 pHq ` C1 pHq.
For x “ px1 , ..., x8 q P F42 ˆ F42 , let x1 :“ px1 , ..., x4 q and x2 :“ px5 , ..., x8 q. Then a code C Ď F42 ˆ F42
is good for H2 if and only if dH px1 , y 1 q ě 3 or dH px2 , y 2 q ě 3 for all x, y P C with x ‰ y.
We conclude the example by showing a structural property of any good code C for H2 with |C| “ 5.
The property will be needed later in Example 5.4.6.
Let C Ď F42 ˆ F42 be any good code for H2 with |C| “ 5. We claim that there are no two codewords
of C that coincide in the first four components. To see this, denote by x, y, z, t, u the elements of C,
and assume by contradiction that, say, x1 “ y 1 . Without loss of generality, we may assume x “ 0
(and thus y 1 “ 0). Then the vectors z 1 , t1 , u1 must have Hamming weight at least 3. Indeed, if, say,
z 1 has Hamming weight smaller than 3, then tx2 , y 2 , z 2 u Ď F42 is a code of cardinality 3 and minimum
Hamming distance 3, contradicting the fact that C1 pHq “ 1. On the other hand, since z 1 , t1 , u1 have
Hamming weight at least 3, we have dH pz 1 , t1 q, dH pz 1 , u1 q, dH pt1 , u1 q ď 2. Since C is good for H2 ,
tz 2 , t2 , u2 u must be a code of cardinality 3 and minimum Hamming distance 3, again contradicting
the fact that C1 pHq “ 1.
4

2.3

Adjacency Structure of a Channel

In this subsection we introduce the adjacency function of a channel, and propose a definition of
isomorphic channels. In particular, we relate the fan-out set description of channels adopted in this
paper with the graph-theoretic approach taken by Shannon in [24].
Definition 2.3.1. The adjacency function αΩ : X ˆ X Ñ t0, 1u of a channel Ω : X 99K Y is defined,
for all x, x1 P X , by
"
1 if Ωpxq X Ωpx1 q ‰ H,
1
αΩ px, x q :“
0 otherwise.
We say that channels Ω1 : X1 99K Y1 and Ω2 : X2 99K Y2 are isomorphic (in symbols, Ω1 – Ω2 ) if
there exists a bijection f : X1 Ñ X2 such that αΩ1 px, x1 q “ αΩ2 pf pxq, f px1 qq for all px, x1 q P X1 ˆ X2 .
The adjacency function of Ω captures the “ambiguity relations” among the input symbols of Ω.
Channels Ω1 and Ω2 are isomorphic if their input symbols have the same ambiguity relations, for some
identification of their input alphabets.
The isomorphism class of a channel Ω : X 99K Y can be represented via a graph G as follows. Up
to a suitable bijection, the vertices of G are the elements of V “ t0, 1, ..., |X | ´ 1u, and px, x1 q P V ˆ V is
an edge of G if and only if αΩ px, x1 q “ 1. Therefore αΩ is precisely the adjacency matrix of the graph
G. This is the way channels are described and studied by Shannon in [24]. Note that, although every
vertex of G is by definition adjacent to itself, loops are usually not shown in the graph description.
Example 2.3.2 (The “pentagon channel”). Let X “ Y :“ t0, 1, 2, 3, 4u, and let Ω : X 99K Y be the
channel defined by
Ωp0q :“ t0, 1u,

Ωp1q :“ t1, 2u,

Ωp2q :“ t2, 3u,

Ωp3q :“ t3, 4u,

Ωp4q :“ t4, 0u.

The five fan-out sets of Ω are represented as in Figure 1(a), and a graph representation of the isomorphism class of Ω is depicted in Figure 1(b). The channel Ω was first introduced and studied by
Shannon in [24].
0

0

1

1

2

2

3

3

4

4

0
1

4

2

(a)

3
(b)

Figure 1: The “pentagon channel:” (a) fan-out sets, (b) graph representation.
One can show that channel isomorphism is an equivalence relation. Moreover, the following properties of isomorphic channels hold. The proof simple and left to the reader.
Proposition 2.3.3. Let Ω1 , Ω2 , Ω3 , Ω4 be channels.
1. If Ω1 – Ω2 and Ω3 – Ω4 , then Ω1 ˆ Ω3 – Ω2 ˆ Ω4 .
2. If Ω1 – Ω2 , then Ωn1 – Ωn2 for all n P Ně1 .

3. If Ω1 – Ω2 , then C1 pΩ1 q “ C1 pΩ2 q.

5

2.4

Zero-Error Capacity

In this subsection we define the zero-error capacity of an adversarial channel, and relate it to the
one-shot capacity. Given the graph-theoretic description of channels illustrated in Subsection 2.3, the
following results essentially already appear in Shannon’s paper [24]. We state them in the language
of fan-out sets for convenience. See [26] for a general reference on Zero-Error Information Theory.
Definition 2.4.1. The zero-error capacity of a channel Ω is the number
C0 pΩq :“ sup tC1 pΩn q{n : n P Ně1 u .
Remark 2.4.2. It is easy to see that C0 pΩq is a non-negative number for every channel Ω, i.e., that
0 ď C0 pΩq ă `8. A less immediate (though intuitive) property is that supremum in the definition of
zero-capacity is in fact a limit. This can be shown using Fekete’s Lemma for superadditive sequences
(see [27] or [28, Section 1.9]).
As one may expect, the zero error-capacity of a channel only depends on its isomorphism class.
This fact follows from property 2 of Proposition 2.3.3.
Proposition 2.4.3. Let Ω1 , Ω2 be channels. If Ω1 – Ω2 , then C0 pΩ1 q “ C0 pΩ2 q.
The next result shows how one-shot capacity and zero-error capacity relate to each other.
Proposition 2.4.4. Let Ω : X 99K Y be a channel. The following hold.
1. C1 pΩn q ě n ¨ C1 pΩq for all n ě 1. Thus C0 pΩq ě C1 pΩq.

2. If C1 pΩq “ 0, then C0 pΩq “ 0.

Proof.
1. Let C Ď X be good for Ω with log2 |C| “ C1 pΩq, and let n P Ně1 . Then C n is good for Ωn .
Thus C1 pΩn q{n ě C1 pΩq. Since n is arbitrary, this implies in particular that C0 pΩq ě C1 pΩq.

2. Since C1 pΩq “ 0, for all x, x1 P X we have Ωpxq X Ωpx1 q ‰ H. Assume by way of contradiction
that C0 pΩq ą 0. Then there exists n P Ně1 with C1 pΩn q ą 0. In particular, there exists a good
code C Ď X n for Ωn with |C| ě 2. Let px1 , ..., xn q, px11 , ..., x1n q P C with px1 , ..., xn q ‰ px11 , ..., x1n q.
Then
H “ pΩpx1 q ˆ ¨ ¨ ¨ ˆ Ωpxn qq X pΩpx11 q ˆ ¨ ¨ ¨ ˆ Ωpx1n qq “

n
ź
˘
`
Ωpxk q X Ωpx1k q ‰ H,

k“1

a contradiction. Therefore it must be that C0 pΩq “ 0, as claimed.

Remark 2.4.5. In general, the zero-error capacity of a channel Ω is strictly larger than its one-shot
capacity. For example, let H be the channel of Example 2.1.5. We showed that C1 pH2 q{2 ą C1 pHq,
which implies that C0 pHq ą C1 pHq.
The zero-error capacity of a channel is a combinatorial invariant which is in general very difficult
to compute.
? For example, let Ω be the pentagon channel of Example 2.3.2. In [24] Shannon showed
that log2 5 ď C0 pΩq ď log2 5 ´ 1. The exact value of C0 pΩq was computed only twenty-three years
?
later by Lovász in [29], using sophisticated Graph Theory techniques. The result is C0 pΩq “ log2 5.

3

Operations with Channels

In this section we introduce two operations with channels, namely, concatenation and union, showing
how they relate to each other and to the channel product. These two constructions will play an
important role throughout the paper in the study of several classes of adversarial point-to-point and
network channels.
6

3.1

Concatenation of Channels

We start with channel concatenation.
Definition 3.1.1. Let Ω1 : X1 99K Y1 and Ω2 : X2 99K Y2 be channels, with Y1 Ď X2 . The
concatenation of Ω1 and Ω2 is the channel Ω1  Ω2 : X1 99K Y2 defined by
ď
pΩ1  Ω2 qpxq :“
Ω2 pyq for all x P X1 .
yPΩ1 pxq

This operation models the situation where the output of Ω1 is taken as the input to Ω2 without
any intermediate processing.
Example 3.1.2. Let Ω : F42 Ñ F42 be the channel introduced in Example 2.1.5. Then for all x P F42
we have pΩ  Ωqpxq “ ty P F42 : dH px, yq ď 2u.
Remark 3.1.3. The isomorphism class of Ω1  Ω2 is not determined in general by the isomorphism
classes of Ω1 and Ω2 , as the following example shows. This crucial difference between channel product
and channel concatenation motivates the choice of the fan-out sets language in this paper.
Example 3.1.4. Let X “ Y :“ t0, 1, 2u. Define the adversarial channels Ω1 , Ω2 : X 99K Y by
Ω1 p0q :“ Ω1 p1q :“ t0, 1u, Ω1 p2q :“ t2u, Ω2 p0q :“ t0u, Ω2 p1q :“ Ω2 p2q :“ t1, 2u. It is easy to see that
Ω1 – Ω2 . However, Ω1  Ω1 ﬂ Ω2  Ω1 , C1 pΩ1  Ω1 q ‰ C1 pΩ2  Ω1 q, and C0 pΩ1  Ω1 q ‰ C0 pΩ2  Ω1 q.
The following result is the analogue of Proposition 2.2.2 for channel concatenation.
Proposition 3.1.5. Let Ω1 , Ω2 , Ω3 be channels. Then:
1. pΩ1  Ω2 q  Ω3 “ Ω1  pΩ2  Ω3 q,

2. C1 pΩ1  Ω2 q ď mintC1 pΩ1 q, C1 pΩ2 qu,
provided that all of the above concatenations are defined.
Proof. Property 1 easily follows from the definition of concatenation. To see property 2, suppose that
Ω1 : X1 99K Y1 and Ω2 : X2 99K Y2 are channels with Y1 Ď X2 . Let C Ď X1 be good for Ω1  Ω2 with
log2 |C| “ C1 pΩ1  Ω2 q. We will show that C is good for Ω1 . Assume that there exist x, x1 P C with
Ω1 pxqXΩ1 px1 q ‰ H, and let y P Ω1 pxqXΩ1 px1 q. Then we have H ‰ Ω2 pyq Ď pΩ1 Ω2 qpxqXpΩ1 Ω2 qpxq,
a contradiction. Therefore C is good for Ω1 , and so C1 pΩ1 q ě log2 |C| “ C1 pΩ1  Ω2 q. On the other
hand, for every x P C we can select yx P Ω1 pxq Ď Y1 . It is easy to check that C 1 :“ tyx : x P Cu Ď X2
is a good code for Ω2 with the same cardinality as C. Therefore C1 pΩ2 q ě C1 pΩ1  Ω2 q.
Note that the associativity of channel concatenation allows expressions such as Ω1  Ω2  Ω3 to
be written without danger of ambiguity.
The following result provides an identity showing that the product of the concatenation of channels is the concatenation of their products. This property and its corollary will be needed later for
the analysis of certain classes of network channels (see Lemma 6.2.3). The proof can be found in
Appendix A, and the result is illustrated in Figure 2.
Proposition 3.1.6. Let n, m P Ně1 , and let Ωk,i be channels, for 1 ď k ď n and 1 ď i ď m. Then
˜
¸
˜
¸
n
n
n
ź
ź
ź
pΩk,1  ¨ ¨ ¨  Ωk,mq “
Ωk,1  ¨ ¨ ¨ 
Ωk,m ,
k“1

k“1

provided that all the above concatenations are defined.

7

k“1

Ω1,1  Ω1,2  ¨ ¨ ¨  Ω1,m
ˆ
Ω2,1  Ω2,2  ¨ ¨ ¨  Ω2,m
ˆ
..
.
ˆ
Ωn,1  Ωn,2  ¨ ¨ ¨  Ωn,m

Ω1,1
Ω1,2
Ω1,m
ˆ
ˆ
ˆ
Ω2,1
Ω2,2
Ω2,m
ˆ  ˆ ¨¨¨ ˆ
..
..
..
.
.
.
ˆ
ˆ
ˆ
Ωn,1
Ωn,2
Ωn,m

“

Figure 2: Illustrating Proposition 3.1.6: a product of concatenations is a concatenation of products.
Corollary 3.1.7. Let Ω be a channel, and let n ě 1 be an integer. Assume that Ω1 , ..., Ωn and
Ω11 , ..., Ω1n are channels for which the concatenation Ωk  Ω  Ω1k is defined for all 1 ď k ď n. Then
˜
¸
˜
¸
n
n
n
ź
ź
ź
1
n
1
pΩk  Ω  Ωk q “
Ωk  Ω 
Ωk .
k“1

k“1

k“1

We can now establish the zero-error analogue of part 2 of Proposition 3.1.5.
Proposition 3.1.8. Let Ω1 : X1 99K Y1 and Ω2 : X2 99K Y2 be channels, with Y1 Ď X2 . We have
C0 pΩ1  Ω2 q ď mintC0 pΩ1 q, C0 pΩ2 qu.
Proof. Fix any integer n ě 1. Combining Proposition 3.1.5 with Proposition 3.1.6 one obtains
C1 ppΩ1  Ω2 qn q “ C1 pΩn1  Ωn2 q ď mintC1 pΩn1 q, C1 pΩn2 qu “ n ¨ min tC1 pΩn1 q{n, C1 pΩn2 q{nu .
Therefore
*
"
"
*
*
"
C1 pΩn1 q C1 pΩn2 q
C1 ppΩ1  Ω2 qn q
ď sup min
: n P Ně1
,
: n P Ně1
sup
n
n
n
"
"
*
"
**
n
C1 pΩ1 q
C1 pΩn2 q
ď min sup
: n P Ně1 , sup
: n P Ně1
n
n
“ mintC0 pΩ1 q, C0 pΩ2 qu,
as claimed.

3.2

Union of Channels

We now define the union of a family of channels having the same input and output alphabets. This
channel operation will be used later in Sections 4 and 6 to study compound adversarial models.
Definition 3.2.1. Let tΩi uiPI be a family of channels, where I is a finite index set and Ωi : X 99K Y
for all i P I. The union of the family tΩi uiPI is the channel denoted as and defined by
¸
˜
ď
ď
ď
Ωi pxq for all x P X .
Ωi : X 99K Y,
Ωi pxq :“
iPI

iPI

iPI

One can check that every channel can be written as the union of deterministic channels. Moreover,
union and concatenation relate to each other as follows. The proof can be found in Appendix A.
Proposition 3.2.2. Let tΩi uiPI be as in Definition 3.2.1. Let Ω1 , Ω2 be channels for which the
concatenation Ω1  Ωi  Ω2 is defined for all i P I (we do not require t1, 2u X I “ H). Then
¸
˜
ď
ď
pΩ1  Ωi  Ω2 q “ Ω1 
Ωi  Ω2 .
iPI

iPI

8

4

Hamming-Type Channels

In this section we study channels whose input alphabet is of the form As , where A is a finite set with
|A| ě 2 (the alphabet), and s P Ně1 . We call these channels “Hamming-type channels”. In the
sequel we work with a fixed alphabet A and a fixed integer s. If u ě 1 is any integer, we write rus
for the set t1, ..., uu. We also define the extended alphabet Â :“ A Y t‹u, where ‹ R A is a symbol
denoting an erasure.
Notation 4.0.1. It is convenient for Hamming-type channels to express the capacity as a logarithm
in base |A|, rather than in base 2. In this paper, if Ω : As 99K Y is a channel, where Y is any output
alphabet, we abuse notation and write C1 pΩq for C1 pΩq ¨ log2 |A|, and C0 pΩq for C0 pΩq ¨ log2 |A|.
The components of a vector x P As are denoted by x “ px1 , ..., xs q. If n ě 1 is an integer, we
denote by px1 , ..., xn q a generic element of pAs qn .

4.1

Error-and-Erasure Adversaries

We start by recalling some well known concepts from classical Coding Theory.
Notation 4.1.1. If u ě 1 is an integer, then the minimum (Hamming) distance of a set C Ď Au
with cardinality |C| ě 2 is dH pCq :“ mintdH px, x1 q : x, x1 P C, x ‰ x1 u.
For all 1 ď d ď u, we set βpA, u, dq :“ 0 if there is no C Ď Au with |C| ě 2 and dH pCq ě d, and
βpA, u, dq :“ maxtlog|A| |C| : C Ď Au , |C| ě 2, dH pCq ě du otherwise.
We will also need the following definitions.
Definition 4.1.2. Let U Ď rss be a set. The U -discrepancy between vectors y P Âs and x P As is
the integer δpy, x; U q :“ |ti P U : yi P A and yi ‰ xi u|. The U -erasure weight of a vector y P Âs is
ω‹ py; U q :“ |ti P U : yi “ ‹u|.
Evidently, if x P As is sent and y P Âs is received, the U -discrepancy measures the number of
errors that occurred in positions indexed by U , while the U -erasure weight measures the number of
erasures that occurred in those positions.
We now describe an adversary having access to a certain set of coordinates U Ď rss, and with
limited error and erasure power.
Definition 4.1.3. Let U Ď rss and t, e ě 0 be integers. The channel Ht,e xU y : As 99K Âs is defined
by
Ht,e xU ypxq :“ ty P Âs : yi “ xi for i R U, δpy, x; U q ď t, ω‹ py; U q ď eu for all x P As .
Note that Ht,e xU y models the scenario where an adversary can erase up to e components with
indices from the set U , and change up to t such components into different symbols from A.
It is well known from classical Coding Theory that C1 pHt,e xrssyq “ βpA, s, 2t ` e ` 1q. We now
generalize this upper bound to the case where the adversary can only operate on a subset U Ď rss.
Proposition 4.1.4. Let U Ď rss be a set of cardinality u :“ |U |, and let t, e ě 0 be integers. Then
C1 pHt,e xU yq “ s ´ u ` βpA, u, 2t ` e ` 1q.
Proof. The result is immediate if U “ H or U “ rss. Assume 0 ă |U | ă s. Denote by π : As Ñ As´u
the projection on the coordinates outside U , and let C Ď As be a capacity-achieving good code for
Ht,e xU y. By restricting the domain and the codomain of π, we obtain a surjective map π : C Ñ πpCq Ď
As´u . It is easy to see that for all z P πpCq we have log|A| |π ´1 pzq| ď βpA, u, 2t ` e ` 1q. We can
9

Ů
write C as a disjoint union C “ zPπpCq π ´1 pzq, from which we see that |C| ď |πpCq| ¨ |A|β , where
β :“ βpA, u, 2t ` e ` 1q. Therefore
log|A| |C| ď log|A| |πpCq| ` βpA, u, 2t ` eq ď s ´ u ` βpA, u, 2t ` eq.

(1)

Finally, the upper bound in (1) is achieved by any code of the form C “ D ˆ As´u , where D Ď Au is a
code with |D| “ 1 if u ď 2t ` e, and a code with log|A| |D| “ βpA, s, uq and minimum distance at least
2t ` e ` 1 otherwise. Note that not all codes C that achieve (1) with equality are of this form.
A more general scenario consists of multiple adversaries acting on pairwise disjoint sets of coordinates with different powers. Such a collection of adversaries can be described as follows.
Definition 4.1.5. Let L ě 1 and U1 , ..., UL Ď rss be pairwise disjoint subsets. Let t1 , ..., tL and
e1 , ..., eL be non-negative integers. Set U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q. The
channel Ht,e xU y : As 99K Âs is defined, for all x P As , by
#
+
L
ď
s
Ht,e xU ypxq :“ y P Â : yi “ xi for i R
Uℓ , δpy, x; Uℓ q ď tℓ , ω‹ py; Uℓ q ď eℓ for all 1 ď ℓ ď L .
ℓ“1

Definition 4.1.5 models a channel with L adversaries associated with pairwise disjoint sets of
coordinates U1 , ..., UL Ď rss. The ℓ-th adversary can erase up to eℓ components of a vector x P As ,
and change up to tℓ such components of x into different symbols from A.
Remark 4.1.6. The channel Ht,e xU y is isomorphic, in the sense of Definition 2.3.1, to a product of
channels. To see this, assume without loss of generality that Uℓ ‰ H for all 1 ď ℓ ď L. Let uℓ :“ |Uℓ |
for all 1 ď ℓ ď L, and denote by πℓ : Âs Ñ Âuℓ the projection on the coordinates in Uℓ . For any
integer r ě 1, we let Idr : Ar 99K Âr be the identity channel (see Example 2.1.4). For 1 ď ℓ ď L, define
the channel Htℓ ,eℓ xUℓ y : Auℓ 99K Âuℓ by Htℓ ,eℓ xUℓ ypxq :“ tπℓ pyq : y P Htℓ ,eℓ xUℓ ypxqu, for all x P As .
Finally, let u :“ |u1 | ` ¨ ¨ ¨ ` |uL |. One can directly check that Ht,e xU y – Ht1 ,e1 xU1 y ˆ ¨ ¨ ¨ ˆ HtL ,eL xUL y
if u “ s, and that Ht,e xU y – Ht1 ,e1 xU1 y ˆ ¨ ¨ ¨ ˆ HtL ,eL xUL y ˆ Ids´u if u ă s.
Remark 4.1.7. The upper bound of Proposition 4.1.4 does not extend additively to multiple adversaries. More precisely, if L, U , t and e are as in Definition 4.1.5, then in general
C1 pHt,e xU yq ­ď s ´

L
ÿ

ℓ“1

|Uℓ | `

L
ÿ

ℓ“1

βpA, uℓ , 2tℓ ` eℓ q,

as the following example shows. This reflects the fact that L adversaries acting on different sets Uℓ ’s,
with error and erasure powers tℓ ’s and eℓ ’s, are not equivalent to a single adversary acting on the set
U1 Y ¨ ¨ ¨ Y UL with error and erasure powers t1 ` ¨ ¨ ¨ ` tℓ and e1 ` ¨ ¨ ¨ ` eℓ , respectively. In particular,
upper bounds from classical Coding Theory do not extend in any obvious way from one to multiple
adversaries.
Example 4.1.8. Take A :“ F2 , L :“ 2, s :“ 8, U1 :“ t1, 2, 3, 4u, U2 :“ t5, 6, 7, 8u, t1 :“ t2 :“ 1
and e1 :“ e2 :“ 0. Let H denote the channel of Example 2.1.5. Then βpF2 , 4, 3q “ C1 pHq “ 1. By
definition of H, we have Ht,e xU y – H ˆ H. Therefore Example 2.2.5 implies
C1 pHt,e xU yq ě log2 5 ą 2 “ s ´

L
ÿ

ℓ“1

10

|Uℓ | `

L
ÿ

ℓ“1

βpA, uℓ , 2tℓ ` eℓ q.

4.2

Compound Channels

In Section 2 we introduced the concepts of (one-shot) capacity and zero-error capacity for general
adversarial channels. We now define a third notion of capacity for the specific class of Hamming-type
channels, which we call the compound zero-error capacity.
Notation 4.2.1. Let L ě 1 be an integer, and let Vℓ Ď rss, for 1 ď ℓ ď L, be sets. If V “ pV1 , ..., VL q,
we define |V | :“ p|V1 |, ..., |VL |q P NL . If Uℓ Ď rss for all 1 ď ℓ ď L and U “ pU1 , ..., Uℓ q, then we write
V Ď U when Vℓ Ď Uℓ for all 1 ď ℓ ď L. Given integer vectors v “ pv1 , ..., vL q, u “ pu1 , ..., uL q P NL ,
we write v ď u if vℓ ď uℓ for all 1 ď ℓ ď L.
Let L ě 1 and U1 , ..., UL Ď rss be pairwise disjoint subsets. Let t1 , ..., tL and e1 , ..., eL be nonnegative integers. Define the L-tuples U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q.
We consider the situation where a channel Ht,e xU y is used n times, but the adversaries are forced
to act on the same sets of coordinates in every channel use. By this we mean that the ℓ-th adversary
freely chooses a set of components Vℓ Ď Uℓ whose size does not exceed tℓ ` eℓ , and operates on
those components in each channel use, according to its error/erasure power. The set of vulnerable
components is unknown to the source, and no feedback is allowed. This scenario can be mathematically
modeled via the channel union operation (see Subsection 3.2) as follows.
Definition 4.2.2. Let L ě 1, U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q be as in
Definition 4.1.5. For n ě 1, the compound channel Ht,e xU yn,cp : pAs qn 99K pÂs qn is defined by
ď
ď
Ht,e xU yn,cp :“
H
Ht,e xV yn .
t,e xV y ˆ ¨ ¨ ¨ ˆ Ht,e xV y “
looooooooooooooomooooooooooooooon
V ĎU
|V |ďt`e

n times

V ĎU
|V |ďt`e

The compound zero-error capacity of the channel Ht,e xU y is the number
C0,cp pHt,e xU yq :“ sup tC1 pHt,e xU yn,cp q{n : n P Ně1 u .

Note that in the definition of compound channel the union is taken over all the V Ď U with
|V | ď t ` e, and not with |V | “ t ` e. This is because, by Definition 4.1.5, we allow tℓ ` eℓ ą |Uℓ |
for some ℓ (so there may be no V Ď U with |V | “ t ` e). This choice may seem unnatural at this
point, but it will simplify the discussion on Hamming-type channels induced by network adversaries
in Subsection 6.2.
The following proposition shows how one-shot capacity, zero-error capacity and compound zeroerror capacity relate to each other. The proof is left to the reader.
Proposition 4.2.3. Let L ě 1, U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q be as in
Definition 4.1.5. For all n ě 1 we have
n ¨ C1 pHt,e xU yq ď C1 pHt,e xU yn q ď C1 pHt,e xU yn,cp q.
In particular,
C1 pHt,e xU yq ď C0 pHt,e xU yq ď C0,cp pHt,e xU yq.

4.3

Capacities of Hamming-Type Channels

The goal of this subsection is to establish the following general theorem on the capacities of a Hammingtype channel of the form Ht,e xU y.

11

Theorem 4.3.1. Let L ě 1, U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q be as in Definition 4.1.5. For all n ě 1 we have
˜
¸
L
ÿ
n
n,cp
n ¨ C1 pHt,e xU yq ď C1 pHt,e xU y q ď C1 pHt,e xU y
q ďn s´
mint2tℓ ` eℓ , |Uℓ |u .
(2)
ℓ“1

In particular,
C1 pHt,e xU yq ď C0 pHt,e xU yq ď C0,cp pHt,e xU yq ď s ´

L
ÿ

ℓ“1

mint2tℓ ` eℓ , |Uℓ |u.

Moreover, all the above inequalities are achieved with equality if A “ Fq and q is sufficiently large.
We will need the following preliminary result, whose proof can be found in Appendix A.
Lemma 4.3.2. Let L ě 1, U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q and e :“ pe1 , ..., eL q be as in Definition 4.1.5. Define σℓ :“ mint2tℓ ` eℓ , |Uℓ |u for all 1 ď ℓ ď L, and σ :“ σ1 ` ¨ ¨ ¨ ` σL ď s.
1

‹

2

1. There exist sets U ℓ , U ℓ , U ℓ Ď Uℓ , for 1 ď ℓ ď L, with the following properties:
1

2

|U ℓ |, |U ℓ | ď tℓ ,

‹

|U ℓ | ď eℓ ,

1

2

‹

|U ℓ Y U ℓ Y U ℓ | “ σℓ for all 1 ď ℓ ď L.

2. We have σ “ |U |, where
ˇ˜
¸ ˜
¸ ˜
¸ˇ
L
L
L
ˇ
ˇ ď
ď
ď
1
2
‹ ˇ
ˇ
U :“ ˇ
Uℓ Y
Uℓ Y
U ℓ ˇ Ď rss.
ˇ
ˇ
ℓ“1

ℓ“1

ℓ“1

3. There exist V “ pV1 , ..., VL q Ď U and V 1 “ pV11 , ..., VL1 q Ď U with the following properties:
• |V |, |V 1 | ď t ` e;
• for any x, x1 P As , if xi “ x1i for all i P rsszU , then Ht,e xV ypxq X Ht,e xV 1 ypx1 q ‰ H.
We can now prove the main result of this section.
Proof of Theorem 4.3.1. Let σℓ :“ mint2tℓ ` eℓ , |Uℓ |u for all 1 ď ℓ ď L, and σ :“ σ1 ` ¨ ¨ ¨ ` σL . We
only show the theorem for σ ă s. The case σ “ s is similar and in fact easier. By Proposition 4.2.3,
it suffices to show that C1 pHt,e xU yn,cp q ď nps ´ σq for all n ě 1, and that for A “ Fq and sufficiently
large q we have C1 pHt,e xU yq ě s ´ σ.
1
2
‹
Let U ℓ , U ℓ , U ℓ (for 1 ď ℓ ď L) and U be as in Lemma 4.3.2. We have σ “ |U |. Denote by
π : As Ñ As´σ the projection on the coordinates outside U . Since σ ă s, the map π is well defined.
Let n ě 1 be an integer. Then π extends component-wise to a map Π : pAs qn Ñ pAs´σ qn . Let
C Ď pAs qn be a capacity-achieving good code for Ht,e xU yn,cp . To obtain the upper bound, it suffices
to show that the restriction of Π to C is injective.
Take x, x1 P C, and assume Πpxq “ Πpx1 q. We will show that x “ x1 . Write x “ px1 , ..., xn q and
1
x “ px11 , ..., x1n q. By definition of Π, we have πpxk q “ πpx1k q for all 1 ď k ď n. By Lemma 4.3.2,
there exist L-tuples of sets V “ pV1 , ..., VL q Ď U and V 1 “ pV11 , ..., VL1 q Ď U such that:
|V |, |V 1 | ď t ` e

and

Ht,e xV ypxk q X Ht,e xV 1 ypx1k q ‰ H

12

for all 1 ď k ď n.

(3)

By definition of Ht,e xU yn,cp we have

Ht,e xU yn,cp pxq X Ht,e xU yn,cp px1 q Ě Ht,e xV yn px1 , ..., xn q X Ht,e xV 1 yn px11 , ..., x1n q
n ´
¯
ź
Ht,e xV ypxk q X Ht,e xV 1 ypx1k q ‰ H,
“
k“1

where the last inequality follows from (3). Since C is good for Ht,e xU yn,cp , we conclude x “ x1 . This
shows that the restriction of Π to C is injective, as desired.
We now prove that the upper bounds in the theorem are tight for A “ Fq and q sufficiently large.
As already stated at the beginning of the proof, it suffices to show that C1 pHt,e xU yq ě s ´ σ.
Let C Ď As be any code with minimum distance dH pCq “ σ ` 1 and cardinality q s´σ . We will
prove that C is good for Ht,e xU y. Let x, x1 P C with x ‰ x1 , and assume by way of contradiction that
there exists z P Ht,e xU ypxq X Ht,e xU ypx1 q. For 1 ď ℓ ď L construct the sets
Uℓ1 :“ ti P Uℓ : zi P A, zi ‰ xi u,

Uℓ2 :“ ti P Uℓ : zi P A, zi ‰ x1i u,

Uℓ‹ :“ ti P Uℓ : zi “ ‹u.

By definition of Ht,e xU y, for all 1 ď ℓ ď L we have |Uℓ1 Y Uℓ2 Y Uℓ‹ | ď mint2tℓ ` eℓ , |Uℓ |u “ σℓ . Note
moreover that Uℓ1 Y Uℓ2 Y Uℓ‹ “ ti P Uℓ : zi ‰ xi or zi ‰ x1i u for all 1 ď ℓ ď L. Since the sets Uℓ ’s are
pairwise disjoint, we have
|t1 ď i ď s : zi “ xi “

x1i u|

“s´

L
ÿ

ℓ“1

|Uℓ1

Y

Uℓ1

Y

Uℓ‹ |

ěs´

L
ÿ

ℓ“1

σℓ “ s ´ σ.

Thus z, x and x1 coincide in at least s´σ components, and therefore dH px, x1 q ď σ, a contradiction.

4.4

Hamming-Type Channels over Product Alphabets

We now consider channels of the form pB m qs 99K pB̂ m qs , where B is a finite set with |B| ě 2, B̂ “ BYt‹u,
‹ R B, m P Ně2 and s P Ně1 . Therefore the input alphabet is A “ B m . For x “ px1 , ..., xs q P pB̂ m qs
and i P rms, we denote by xi “ pxi,1 , ..., xi,m q the sub-components of xi .

Definition 4.4.1. For y P B̂ m and x P B m , we let δpy, xq :“ |ti P rms : yi P B and yi ‰ xi u| be the
discrepancy between y and x. The erasure weight of y P B̂ m is ω‹ pyq :“ |ti P rms : yi “ ‹u|.
Consider an adversary who has access to all the s components of x “ px1 , ..., xs q P pB m qs . For each
component xi P B m , the adversary can corrupt up to t sub-components of xi , and erase at most e of
them. This scenario is modeled as follows.

Definition 4.4.2. Let t, e ě 0 be integers. The channel Ht,e xB, m, sy : pB m qs 99K pB̂ m qs is defined,
for all x “ px1 , ..., xs q P pB m qs , by
Ht,e xB, m, sypxq :“ ty P pB̂ m qs : δpyi , xi q ď t and ω‹ pyi q ď e for all 1 ď i ď su.

We conclude this section computing the capacity and the zero-error capacity of a channel of the
form Ht,e xB, m, sy. In the following theorem capacities are expressed as logarithms in base |A| “ |B|m .

Theorem 4.4.3. Let t, e ě 0 be integers. For all n ě 1 we have

n ¨ C1 pHt,e xB, m, syq ď C1 pHt,e xB, m, syn q ď n ¨ s{m ¨ maxt0, m ´ 2t ´ eu.

In particular,
C1 pHt,e xB, m, syq ď C0 pHt,e xB, m, syq ď s{m ¨ maxt0, m ´ 2t ´ eu.

Moreover, all the above inequalities are achieved with equality if A “ Fq and q is sufficiently large.

Proof. It follows from the definitions that the channel Ht,e xB, m, sy coincides with the s-th power of
the Hamming-type channel Ht,e xrmsy : B m 99K B̂ m of Definition 4.1.3 (over the alphabet B and with
input symbols from B m ). Similarly, the n-th power of Ht,e xB, m, sy coincides with the ns-th power of
Ht,e xrmsy : B m 99K B̂ m . Therefore the desired statement follows from Theorem 4.3.1.
13

5

Networks, Adversaries, and Capacity Regions

In this section we start the analysis of networks by studying combinational networks, network alphabets, network codes, and adversaries. We show that these objects naturally induce families of
adversarial channels, which determine the capacity regions of multi-source network under various
adversarial models.

5.1

Combinational Networks

In the sequel, A denotes a finite set with cardinality |A| ě 2, which we call the network alphabet.
A network is defined as follows.
Definition 5.1.1. A (combinational) network is a 4-tuple N “ pV, E, S, Tq where:
(A) pV, Eq is a finite directed acyclic multigraph,
(B) S Ď V is the set of sources,

(C) T Ď V is the set of terminals or sinks.
Note that we allow multiple parallel directed edges. We also assume that the following hold.
(D) |S| ě 1, |T| ě 1, S X T “ H.

(E) For any S P S and T P T there exists a directed path from S to T .

(F) Sources do not have incoming edges, and terminals do not have outgoing edges.

(G) For every vertex V P VzpS Y Tq there exists a directed path from S to V for some S P S, and a
directed path from V to T for some T P T.
The elements of V are called vertices. The elements of VzpS Y Tq are the intermediate vertices.
We denote the set of incoming and outgoing edges of a V P V by inpV q and outpV q, respectively.
We are interested in multicast problems over networks of type N “ pV, E, S, Tq. Our model
will encompass the presence of one or multiple adversaries, capable of corrupting the values of some
network edges, or erasing them, according to certain restrictions.
The sources attempt to transmit information packets to all the terminals simultaneously, sharing
the network resources. The packets are drawn from the network alphabet A. The intermediate vertices
emit packets that belong to the same alphabet A, but collect over the incoming edges packets that
belong a priori to the extended network alphabet Â “ A Y t‹u, where ‹ R A is a symbol denoting
an erasure.
Remark 5.1.2. The symbol ‹ from the extended alphabet Â should not be regarded as an ordinary
alphabet symbol, but more as an “erasure warning” symbol. This is the reason why we force the
intermediate vertices to emit packets from A, rather than Â. If vertices were allowed to emit any
symbol from Â, the whole theory would simply reduce to that of a network with a larger alphabet.
We assume that every edge of N can carry precisely one element from A, or possibly the erasure
symbol ‹. For examples, if the sources transmit vectors of length m with entries from a finite field Fq ,
then A “ Fm
q , and each edge carries m log 2 pqq bits (and possibly the symbol ‹).
In every network use, an intermediate vertex collects packets over the incoming edges, processes
them, and sends out packets over the outgoing edges. The outgoing packets are a function of the
incoming packets. We assume that the intermediate vertices are memoryless, and all network transmissions are delay-free.
Removing idle edges if necessary, we may also assume without loss of generality that every vertex
sends information packets over every outgoing edge. Along with property (G) of Definition 5.1.1, this
ensures in particular that every non-source vertex receives a packet on each of its incoming edges.
14

Notation 5.1.3. In the sequel we work with a fixed combinational network N “ pV, E, S, Tq. We
choose an enumeration for the sources of N , say S “ tS1 , ..., SN u, and let I :“ t1, ..., N u be the set of
source indices. For J Ď I, we let SJ :“ tSi : i P Ju. For all i P I, the local input alphabet of source
Si P S is Xi :“ A|outpSi q| . The global input alphabet of the network N is X :“ X1 ˆ ¨ ¨ ¨ ˆ XN .
The topology of N induces a partial order ĺ on E as follows. For e, e1 P E, we have e ĺ e1 if and
only if there exists a directed path in N whose first edge is e and whose last edge is e1 . Since N is a
directed and acyclic graph, ĺ is well defined. Such partial order can be extended to a total order on
E (see [30, Section 22]). Throughout this paper, we fix such an order extension and denote it by ď.
Remark 5.1.4. The choice of the linear order ď will prevent ambiguities in the interpretation of the
objects associated with N . None of the results in this paper depends on the specific choice of ď.

5.2

Network Codes and Network Channels

As mentioned in Subsection 5.1, each intermediate vertex of N applies some function to the incoming
packets, and transmits the value of this function on the outgoing edges. The collection of operations
that the intermediate vertices perform is called the network code.
Definition 5.2.1. A network code F for N is a family of functions tFV : V P VzpS Y Tqu, where
FV : Â|inpV q| Ñ A|outpV q|

for all V P VzpS Y Tq.

Assume A “ Fm
q for some prime power q and some integer m ě 1. Then we say that F is
linear if for all vertices V P VzpS Y Tq there exists a |inpV q| ˆ |outpV q| matrix LV over Fq such that
r
FV px1 , ..., xr q “ py1 , ..., ys q for all px1 , ..., xr q P pFm
q q , where r :“ |inpV q|, s :“ |outpV q|, and
` J
˘
`
˘
y1 ¨ ¨ ¨ ysJ :“ xJ
¨ ¨ ¨ xJ
r ¨ LV .
1

r
In other words, we require that the restriction of FV : Âr Ñ As to Ar “ pFm
q q is a function that
returns linear combinations of the r input vectors from Fm
q . When F is a linear network code and
V P VzpS Y Tq, we sometimes denote the matrix LV simply by FV .

A collection of functions as in Definition 5.2.1 fully specifies the operations performed by the
vertices of N with no ambiguity, thanks to the choice of the linear order ď. Note that in this paper we
do not require our network codes to be linear (the alphabet A may not even be of the form A “ Fm
q ).
In the remainder of the section we define a series of deterministic channels that are naturally
induced by a network code F for N .
Definition 5.2.2. Let F be a network code for N , and let E 1 Ď E be a non-empty set of edges. In
an error-free context, by definition of network code, the values of the edges from E 1 can be expressed
as function of the sources input x P X “ X1 ˆ ¨ ¨ ¨ XN . This defines a deterministic channel
ź
1
ΩF rS Ñ E 1 s :
Xi 99K A|E | ,
iPI

that associates to x P X the alphabet packets observed over the edges in E 1 , ordered according to ď.
1
Note that ΩF rS Ñ E 1 spxq Ď A|E | is a set of cardinality one for all x P X “ X1 ˆ ¨ ¨ ¨ XN .
Now assume that T P T, and that E 1 is a cut that separates all sources S1 , ..., SN from T . We will
construct a deterministic channel that describes the transfer from the edges in E 1 to the terminal T .
Recall from Poset Theory that e P E covers e1 P E when e1 ň e, and there is no e2 P E with
1
e ň e2 ň e. We recursively define the sets of edges
E01 :“ inpT q,

1
Ek`1
:“ pE 1 X Ek1 q Y te1 P E : there exists e P Ek1 zE 1 that covers e1 u for k P Ně1 .

15

1
is the union of E 1 X Ek1 and the set of network edges that immediately precede the
For all k P N, Ek`1
edges in Ek1 zE 1 . Let k :“ mintk P N : Ek1 Ď E 1 u, where the minimum is well defined by property (G) of
Definition 5.1.1 and the fact that E 1 is a cut that separates S and T .
For all 0 ď k ď k ´ 1, the values of the edges in Ek1 can be expressed, via the network code F, as
1
a function of the values of the edges in Ek`1
. This defines k functions ΨF rks : Â|Ek`1 | Ñ A|Ek | , for
0 ď k ď k ´ 1 (see also the following Example 5.2.3). Note that we define ΨF rks to be the identity on
1
the edges in the set Ek1 X Ek`1
. Now the composition Ψ :“ ΨF rk ´ 1s ˝ ¨ ¨ ¨ ˝ ΨF r1s ˝ ΨF r0s expresses
the values of the edges of inpT q as a function of the values of the edges from Ek1 Ď E 1 . We trivially
extend Ψ to a function
1
Ψ : A|E | Ñ A|inpT q|

that expresses the values of the edges from inpT q as a function of the values of the edges from the
edge-cut E 1 (by “trivially” we mean that the value of the edges from E 1 zEk1 play no role in the definition
of Ψ). This induces a deterministic channel denoted by
1

ΩF rE 1 Ñ inpT qs : Â|E | 99K A|inpT q| .
Example 5.2.3. Let N be the network in Figure 3. The edges of N are ordered according to their
indices. The set E 1 :“ te2 , e5 u is an edge-cut between S “ tSu and T . The edges in E 1 are represented
by a dashed arrow in Figure 3. Fix a network code F for N .
e1

S

e2

V1

e3

V2

e5

e6

V3

e7

T

e4

Figure 3: Network for Example 5.2.3.
E21

Following the notation of Definition 5.2.2, we have E01 “ inpT q “ te6 , e7 u, E11 “ te4 , e5 u, and
“ te2 , e5 u “ E 1 . Hence k “ 2. The functions ΨF r0s and ΨF r1s are as follows:
ΨF r0spx4 , x5 q “ FV3 px4 , x5 q P A2
1

and

ΨF r1spx2 , x5 q “ pFV21 px2 q, x5 q P A2

1

for all px4 , x5 q P Â|E1 | “ Â2 and px1 , x5 q P Â|E2 | “ Â2 , and where FV21 px2 q is the second component of
˘
`
the vector FV1 px2 q P A2 . Now observe that pΨF r1s ˝ ΨF r0sq px2 , x5 q “ FV3 FV21 px2 q, x5 P A2 for all
px2 , x5 q P Â2 , which expresses the values of the edges of `inpT q as a function
of the values of the edges
˘
1
1
2
2
of E . Therefore one has ΩF rE Ñ inpT qspx2 , x5 q “ tFV3 FV1 px2 q, x5 u Ď A for all px2 , x5 q P Â2 .

Remark 5.2.4. The deterministic channels introduced in Definition 5.2.2 are well defined for any
edge-cut E 1 that separates the network sources from T . In particular, we do not require E 1 to be a
minimum cut or an antichain cut (i.e., a cut where every two distinct edges are not comparable with
respect to the order ĺ). For example, the cut E 1 of Example 5.2.3 is not an antichain, as e2 ĺ e5 .
Observe moreover that whenever E 1 is a non-antichain cut, the channel ΩF rE 1 Ñ inpT qs automatically
gives “priority” to the edges in E 1 that are “closer” to the destination T in the network topology.
The specific definition of the channel ΩF rE 1 Ñ inpT qs makes it so that all the results of this paper
(such as decomposition results and upper bounds) also hold for edge-cuts that do not form an antichain
with respect to ĺ. This is different, e.g., from the general approach of [2], where some of the cut-set
bounds are derived only for the special case of antichain edge-cuts (see in particular [1, Theorem 3]).
Remark 5.2.5. If T P T and E 1 is a cut between S and T , then the channel describing the transfer
from S to T factors through the cut E 1 , i.e., we have
ΩF rS Ñ inpT qs “ ΩF rS Ñ E 1 s  ΩF rE 1 Ñ inpT qs.
16

Notice that for a non-antichain cut E 1 the above channel decomposition does not simply follow from
the fact that E 1 is a cut between S and inpT q, and heavily relies on the specific construction of the
channel ΩF rE 1 Ñ inpT qs given in Definition 5.2.2.
Example 5.2.6. Following the notation of Example 5.2.3, it is easy to see that for all px1 , x2 q P A2
we have ΩF rS Ñ E 1 spx1 , x2 q “ tpx2 , FV2 px1 , FV1 1 px2 qqqu, where FV1 1 px2 q is the first component of
FV1 px2 q P A2 . Using the expression for ΩF rE 1 Ñ inpT qs found in Example 5.2.3 we obtain
pΩF rS Ñ E 1 s  ΩF rE 1 Ñ inpT qsq px1 , x2 q “ tFV3 pFV21 px2 q, FV2 px1 , FV1 1 px2 qqqu for all px1 , x2 q P A2 ,
which expresses the values of the edges from inpT q as a function of the values of the source edges.
We now examine channels that are obtained by “freezing” the packets emitted by some of the
network sources. These deterministic channels will play an important role in the study of the capacity
region of adversarial networks in Section 6.
Definition 5.2.7. Let F be a network
ś code for N , and let J Ĺ I be a proper non-empty subset of
source indices. Fix an element x P iPIzJ Xi , and let E 1 Ď E be non-empty. We denote by
ź
1
Xi 99K A|E |
ΩJF rSJ Ñ E 1 | xs :
iPJ

ś
1
the deterministic channel that associates to an input x P iPJ
ś Xi the values of the edges from E when
the sources in SJ emit the corresponding
ś packets from x P iPJ Xi , and the sources in SIzJ emit the
corresponding (fixed) packets from x P iPIzJ Xi .
Let T P T be a terminal, and let E 1 be a cut that separates SJ from T . Reasoning as in Definition 5.2.2, it is easy to see that the values of the edges from inpT q can be expressed, given the network
code F, as a function of the values of the edges from E 1 and by x. This defines a deterministic channel
1

ΩJF rE 1 Ñ inpT q | xs : Â|E | 99K A|inpT q| .
Remark 5.2.8. The channel describing the transfer from SJ to T , given the input x, again factors
through any cut E 1 between SJ and T , i.e.,
ΩJF rSJ Ñ inpT q | xs “ ΩJF rSJ Ñ E 1 | xs  ΩJF rE 1 Ñ inpT q | xs.

5.3

Network Adversaries

We now model combinatorially an adversary capable of corrupting the values of the edges of N , or
erase them, according to certain restrictions. We denote such an adversary by A, and call the pair
pN , Aq an adversarial network. The vertices still process the incoming packets using a network
code F.
We start by defining some adversarial analogues of the deterministic channels introduced in Definitions 5.2.2 and 5.2.7.
Definition 5.3.1. Let F be a network code for N , and let T P T be a terminal. We denote by
ź
ΩF rA; S Ñ inpT qs :
Xi 99K Â|inpT q|
iPI

ś

the channel that associates to an input x P iPI Xi the variety of packets that can be observed over
the edges of inpT q in the presence of the adversary A. Similarly, when J Ď I is a non-empty subset
of source indices, we denote by
ź
Xi 99K Â|inpT q|
ΩJF rA; SJ Ñ inpT q | xs :
iPJ

17

ś
the channel that associates to x P iPJ Xi the variety of packets that can be observed over the edges
from E 1 when,
in the presence of the adversary A, the sources in SJ emit the corresponding
ś
ś packets
from x P iPJ Xi , and the sources in SIzJ emit the corresponding (fixed) packets from x P iPIzJ Xi .
Clearly, the adversarial channels introduced in Definition 5.3.1 are not deterministic in general.

Example 5.3.2. Let N be the network depicted in Figure 4. We order the edges of N according
to their indices. The input alphabet is X “ X1 ˆ X2 “ A2 ˆ A. A network code F for N is the
assignment of a function FV : Â2 ˆ Â Ñ A4 .
S1

e1
e2

e3

e4
e5
e6
e7

V

S2

T

Figure 4: Network for Example 5.3.2.
Consider an adversary A able to erase at most one of the values of the dotted edges of N , i.e.,
te4 , e6 , e7 u. This scenario is modeled by a channel ΩF rA; S Ñ inpT qs : A2 ˆ A 99K Â4 . We can
describe this channel as follows. If px1 , x2 , x3 q P A2 ˆ A and z :“ FV px1 , x2 , x3 q P A4 , then
ΩF rA; S Ñ inpT qspx1 , x2 , x3 q “ ty P Â4 : y2 “ z2 and ω‹ py; t1, 2, 3, 4uq ď 1u,
where ω‹ is the erasure weight of Definition 4.1.2. Now let J :“ t1u, and assume that S2 emits a
fixed element x3 P A. The channel ΩJF rA; SJ Ñ inpT q | x3 s is as follows. If px1 , x2 q P A2 , and z :“
FV px1 , x2 , x3 q P A4 , then ΩJF rA; S Ñ inpT qspx1 , x2 q “ ty P Â4 : y2 “ z 2 and ω‹ py; t1, 2, 3, 4uq ď 1u.
We conclude this subsection by introducing a general class of network adversaries, acting on sets
of edges with limited error and erasure power.
Notation 5.3.3. Let U Ď E be a set of network edges, and let t, e ě 0 be integers. We denote by
At,e xU y an adversary having access only to edges from U , being able to erase up to e of them, and
change the values of up to t of them with different symbols from A.
Let L ě 1 be an integer, and let U1 , ..., UL Ď E be pairwise disjoint subsets of network edges. Let
t1 , ..., tL and e1 , ..., eL be non-negative integers. Define the L-tuples U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q
and e :“ pe1 , ..., eL q. We denote by At,e xU y the adversary representing the scenario where all the
Atℓ ,eℓ xUℓ y’s act simultaneously on the network, possibly with coordination.

5.4

Capacity Regions of Adversarial Networks

In this section, in analogy with the theory of point-to-point adversarial channels, we propose definitions
of one-shot, zero-error, and compound zero-error capacity regions of adversarial networks.
The one-shot capacity region, as the name suggests, measures the number of alphabet symbols
that the sources can multicast to all terminals in a single use of the network. The zero-error capacity
region measures the average number of packets that can be multicasted to the terminals per network
use, in the limit where the number of uses goes to infinity. Finally, the compound zero-error capacity
regions measures the average number of packets that can be multicasted to the terminals per network
use, in the limit where the number of uses goes to infinity, and in the scenario where the adversary is
forced to operate on the same (unknown) set of edges in every network use.

18

Remark 5.4.1. A definition of capacity region was proposed in [23, Section IV] in the context of
adversarial random network coding. The definition of [23] is probabilistic, and best suited to study
random linear approaches to multicast. In particular, it does not coincide with the notion of capacity
originally proposed in [2] for single-source adversarial networks (see, e.g., [2, Theorem 1]). Inspired by
the work of Shannon [24], our approach to adversarial network channels has a combinatorial flavor,
rather than a probabilistic one. As a consequence, the three notions of capacity region introduced in
this paper are all different from the one proposed in [23], and thus require an independent analysis.
Definition 5.4.2. The (one shot) capacity region of pN , Aq is the set R1 pN , Aq of all the N tuples pα1 , ..., αN q P RN
ě0 for which there exist a network code F for N and non-empty sets Ci Ď Xi ,
for 1 ď i ď N , with the following properties:
1. log|A| |Ci | “ αi ,

2. C “ C1 ˆ ¨ ¨ ¨ ˆ CN is good for each channel ΩF rA; S Ñ inpT qs, T P T.
We say that such a pair pF, Cq achieves the rate pα1 , ..., αN q in one shot.
The conditions in Definition 5.4.2 guarantee that the sources can transmit in one shot to each of
the sinks α1 ` ¨ ¨ ¨ ` αN alphabet symbols, αi of which are emitted by Si , for 1 ď i ď N . Note that
the code C is by definition a cartesian product. This models the scenario where the sources cannot
coordinate.
Remark 5.4.3. Let n ě 1 be an integer. The n-th cartesian power X n “ pX1 ˆ ¨ ¨ ¨ ˆ XN qn can be
naturally identified with the set X1n ˆ ¨ ¨ ¨ ˆ XNn . Therefore
if T P T and F 1 , ..., F n are network codes
śn
for N , we can see a product channel of the form k“1 ΩF k rA; S Ñ inpT qs as a channel
n
ź

k“1

ΩF k rA; S Ñ inpT qs : X1n ˆ ¨ ¨ ¨ ˆ XNn 99K Â|inpT q| .

(4)

We now introduce the zero-error capacity region.
Definition 5.4.4. The zero-error capacity region of pN , Aq is the closure R0 pN , Aq of the set
R0 pN , Aq of all the N -tuples pα1 , ..., αN q P RN
ě0 for which there exist:
• an integer n ě 1,

• network codes F 1 , ..., F n for N ,
• non-empty sets Ci Ď Xin , for 1 ď i ď N ,
with the following properties:
1. log|A| |Ci | “ n ¨ αi ,

2. C “ C1 ˆ ¨ ¨ ¨ ˆ CN is good for each channel

n
ź

k“1

ΩF k rA; S Ñ inpT qs, T P T, in the sense of (4).

Remark 5.4.5. When the network vertices operate in a memoryless way (as in our setup) or, more
generally, in a causal way, then doubling the length of the network messages (i.e., assuming that the
alphabet is A ˆ A instead of A) does not model two uses of the network, as the following example
shows. More generally, taking the n-th power of the the network alphabet does not model n network
uses. As a consequence, the zero-error capacity region is not the same as the one-shot capacity region,
in the limit where the “length” of the network alphabet goes to infinity. These two capacity concepts
are different in general, and require independent analyses.

19

Example 5.4.6. Let N be the network in Figure 5, and let A :“ F2 be the network alphabet. The
edges are ordered according to their indices. Consider an adversary on N who can only operate on
the edges from E 1 “ te3 , e4 , e5 , e6 u by possibly corrupting the value of one of these edges. The action
of the adversary is described by the channel H : F42 99K F42 of Examples 2.1.5 and 2.2.5, given by
Hpxq “ ty P F42 : dH py, xq ď 1u for all x P F42 . Observe that a network code for N is the assignment of
a function FV : F22 Ñ F42 , as erasures are excluded from the model.
e3
e4
e5
e6

e1

S

e2

V

T

Figure 5: Network for Example 5.4.6.
Assume that the network is used twice, with network codes F 1 and F 2 in the first and second
channel use, respectively. The channel describing the two uses of the network is the product channel
Ω1 :“ pΩF 1 rS Ñ E 1 s  Hq ˆ pΩF 2 rS Ñ E 1 s  Hq : F22 ˆ F22 99K F42 ˆ F42 .
Note that for all x “ px1 , x2 , x3 , x4 q P F22 ˆ F22 we have Ω1 pxq “ H2 pFV1 px1 , x2 q, FV2 px3 , x4 qq. We will
show that C1 pΩ1 q ă log2 5. Assume by contradiction that there exists a code C Ď F22 ˆ F22 with |C| “ 5
and which is good for Ω1 . Then C :“ tpFV1 px1 , x2 q, FV2 px3 , x4 qq : x “ px1 , x2 , x3 , x4 q P Cu Ď F42 ˆ F42 is
a good code for the channel H2 of cardinality five. Since |C| “ 5, there must exist x, x1 P C with x ‰ x1
and px1 , x2 q “ px11 , x12 q. Therefore C Ď F42 ˆ F42 is a good code for H2 of cardinality five which has two
distinct codewords that coincide in the first four components. However, as shown in Example 2.2.5,
there is no such a code. Thus C1 pΩ1 q ă log2 5, as claimed.
Now assume that the edges can carry symbols from F2 ˆF2 . Using Example 2.2.5 one can show that
there exists a function FV : F22 ˆ F22 Ñ F42 ˆ F42 such that Ω2 :“ ΩF rS Ñ E 1 s  H2 : F22 ˆ F22 99K F42 ˆ F42
has capacity C1 pΩ2 q ě log2 5. Therefore C1 pΩ2 q ą C1 pΩ1 q.
We now focus on composite adversaries of type At,e xU y, where L ě 1, and U , t and e are as in
Notation 5.3.3. Consider the scenario where the network N is used multiple times, and where the L
network adversaries At1 ,e1 xU1 y, ..., AtL ,eL xUL y defining At,e xU y are forced to operate on the same set
of edges in each use of the network. In analogy with Definition 4.2.2, this scenario naturally motivates
the following definition.
Definition 5.4.7. Let L ě 1, U , t and e be as in Notation 5.3.3, and assume A “ At,e xU y. The
compound zero-error capacity region of pN , Aq is the closure R0,cp pN , Aq of the set R0,cp pN , Aq
of all the N -tuples pα1 , ..., αN q P RN
ě0 for which there exist:
• an integer n ě 1,

• network codes F 1 , ..., F n for N ,
• non-empty sets Ci Ď Xin , for 1 ď i ď N ,
with the following properties:
1. log|A| |Ci | “ n ¨ αi ,

2. C “ C1 ˆ ¨ ¨ ¨ ˆ CN is good for each channel

ď

n
ź

VĎU k“1
|V|ďt`e

ΩF k rAt,e xVy; S Ñ inpT qs, T P T.

Remark 5.4.8. It follows from the definitions that RpN , Aq Ď R0 pN , Aq Ď R0 pN , Aq for any
adversary A. Moreover, if A is of the form A “ At,e xU y, then R0 pN , Aq Ď R0,cp pN , Aq. In particular,
20

we have R0 pN , Aq Ď R0,cp pN , Aq. This property formalizes the fact that, in the compound model,
the adversaries are forced to operate on the same edges in each channel use, and therefore their power
is possibly reduced.

6

Porting Bounds for Hamming-Type Channels to Networks

In this section we show how the properties of channel products, concatenations and unions established
in Section 3 can be combined with each other to obtain upper bounds for the three capacity regions
of an adversarial network. The idea behind our approach is to derive cut-set bounds by porting, in a
systematic manner, upper bounds for the three capacities of Hamming-type channels to networks.
Notation 6.0.1. In the sequel we follow the notation of Section 5, and fix a network N “ pV, E, S, Tq
with alphabet A. The sources are S “ tS1 , ..., SN u, and I “ t1, ..., N u is the set of source indices.
The alphabet of source Si is Xi :“ A|outpSi q| , for 1 ď i ď N , and X :“ X1 ˆ ¨ ¨ ¨ ˆ XN . We work with a
generic adversary A and a fixed linear extension ď of the network partial order ĺ.

6.1

Method Description

Suppose that we are interested in describing the one-shot capacity region RpN , Aq Ď RN
ě0 of pN , Aq.
Let pα1 , ..., αN q P RpN , Aq be arbitrary. By Definition 5.4.2, there exist a network code F for N and
a code C “ C1 ˆ ¨ ¨ ¨ ˆ CN Ď X1 ˆ ¨ ¨ ¨ ˆ XN such that pF, Cq achieves pα1 , ..., αN q in one shot.
1
Let J Ĺ I be a non-empty subset of source indices,
ś and let T P T be a terminal. Take a cut E Ď E
that separates SJ from T , and fix an element x P iPIzJ Ci . Assume for the moment that there is no
adversary A. As observed in Remark 5.2.8, the channel ΩJF rSJ Ñ inpT q | xs decomposes as follows:
ΩJF rSJ Ñ inpT q | xs “ ΩJF rSJ Ñ E 1 | xs  ΩJF rE 1 Ñ inpT q | xs.
1

(5)

1

Denote by IdrE 1 Ñ E 1 s : A|E | 99K Â|E | the identity channel (see Example 2.1.4), and observe that
equation (5) can be trivially re-written as
ΩJF rSJ Ñ inpT q | xs “ ΩJF rSJ Ñ E 1 | xs  IdrE 1 Ñ E 1 s  ΩJF rE 1 Ñ inpT q | xs.

(6)

We now let the adversary A act only on the cut E 1 , and assume that its action on the edges of E 1
1
1
can be described by a channel ΩrA; E 1 Ñ E 1 s : A|E | 99K Â|E | .
For example, if A was originally able to corrupt the values of up to t edges of N , we now consider
the scenario where A can corrupt up to t edges from E 1 . This action is described by the Hamming-type
1
1
channel Ht,0 xU y : A|E | 99K Â|E | introduced in Definition 4.1.3, with s :“ |E 1 | and U :“ rss “ t1, ..., su.
Therefore we can simply take ΩrA; E 1 Ñ E 1 s :“ Ht,0 xU y in this case.
Going back to our general discussion, observe that letting the adversary A operate only on E 1
replaces the channel IdrE 1 Ñ E 1 s in (6) with the channel ΩrA; E 1 Ñ E 1 s. This defines a new channel
J

ΩF rA; SJ Ñ inpT q | xs :“ ΩJF rSJ Ñ E 1 | xs  ΩrA; E 1 Ñ E 1 s  ΩJF rE 1 Ñ inpT q | xs,

(7)

whose decomposition is graphically represented in Figure 6, for a fixed x.
J
Note that ΩF rA; SJ Ñ inpT q | xs is finer than ΩJF rA; SJ Ñ inpT q | xs, as in the former channel
the action of the adversary was restricted to E 1 . In symbols (see Definition 2.1.6) we have
J

ΩF rA; SJ Ñ inpT q | xs ď ΩJF rA; SJ Ñ inpT q | xs.
(8)
ś
ś
Now observe that the code iPJ Ci is good for the channel ΩJF rA; SJ Ñ inpT q | xs. Indeed,
iPI Ci
ś
is a good code for ΩF rA; S Ñ inpT qs by definition of one-shot capacity region, and x P iPIzJ Ci .
21

ΩrA; E 1 Ñ E 1 s

ΩJF rSJ Ñ E 1 | xs

SJ

T

.. 1
. E

ΩJF rE 1 Ñ inpT q | xs
J

Figure 6: Decomposition of the channel ΩF rA; SJ Ñ inpT q | xs.
ś

J

Ci is good for the channel ΩF rA; SJ Ñ inpT q | xs as well. In particular,
ˇ
ˇ
ˇź ˇ
¯
´
ÿ
J
ˇ
ˇ
(9)
αi “ log|A| ˇ Ci ˇ ď C1 ΩF rA; SJ Ñ inpT q | xs ď C1 pΩrA; E 1 Ñ E 1 sq,
ˇ
ˇ

Using (8), we see that

iPJ

iPJ

iPJ

where C1 denotes the one-shot capacity (expressed as a logarithm in base |A|), and the last inequality
follows combining equation (7) and Proposition 3.1.5. We therefore obtained in (9) an upper-bound
for the capacity region RpN , Aq in terms of the capacity of the intermediate channel ΩrA; E 1 Ñ E 1 s :
1
1
A|E | 99K Â|E | , which does not depend on the specific choice of the network code F.
A similar (and in fact easier) argument can be given for the case J “ I, i.e., when all sources are
considered. In that case there is no x to select.
Example 6.1.1. Let N be the network in Figure 7. The edges of N are ordered according to their
indices. We consider an adversary A who can corrupt up to one packet from the dotted edges, i.e.,
from U :“ te1 , e4 , e6 , e7 u. Therefore A “ A1,0 xU y according to Notation 5.3.3 (erasures are excluded
from the model). Let pα1 , α2 q P RpN , Aq be arbitrary.
S1

e1
e2

e3

e4
e5
e6
e7

V

S2

T

Figure 7: Network for Example 6.1.1.
Take J “ t1u. The set E 1 “ te4 , e5 , e6 , e7 u is a cut between S1 and T . Let U :“ t1, 3, 4u, and let
H1,0 xU y denote the channel introduced in Definition 4.1.3. Using (9) we obtain α1 ď C1 pH1,0 xU yq,
and by Theorem 4.3.1 we have C1 pH1,0 xU yq ď 4 ´ 2 ¨ 1 “ 2. Therefore α1 ď 2. Reasoning in the same
way with the cut E 1 “ te1 , e2 u, one obtains a better bound for α1 , i.e., α1 ď 1.
Taking J “ t2u and J “ t1, 2u, and combining in the same way (9) and Theorem 4.3.1, we obtain
α2 ď 1 and α1 ` α2 ď 2. Therefore RpN , Aq Ď tpα1 , α2 q P R2ě0 : α1 ď 1, α2 ď 2, α1 ` α2 ď 1u.

6.2

Porting Lemmas

We now establish two general lemmas that formalize the argument presented in Subsection 6.1, and
extend it to the zero-error and to the compound zero-error capacity regions. Note that these extensions
do not directly follow from the discussion in the previous subsection, and heavily rely on the properties
of channel concatenation and union established in Section 3. We start with the Porting Lemma for
the one-shot and the zero-error capacity.
Lemma 6.2.1. Let tΩrA; E 1 Ñ E 1 s : E 1 Ď E, E 1 ‰ Hu be a family of adversarial channels such that
1
1
ΩrA; E 1 Ñ E 1 s : A|E | 99K Â|E | for all E 1 . Assume that for all network codes F for N :
22

• ΩF rA; S Ñ inpT qs ď ΩF rS Ñ E 1 s  ΩrA; E 1 Ñ E 1 s  ΩF rE 1 Ñ inpT qs for all T P T and for all
cuts E 1 Ď E that separate S from T ;

1
• ΩJF rA; SJ Ñ inpT q | xs ď ΩJF rSJ Ñ E 1 | xs  ΩrA; E 1 Ñ E 1 s  ΩJF rE
ś Ñ inpT q | xs for all
1
non-empty J Ĺ I, all cuts E Ď E that separate SJ from T , and all x P iPIzJ Xi .

The following hold.

1. For all pα1 , ..., αN q P RpN , Aq and for all non-empty subset J Ď I we have
ÿ
αi ď min mintC1 pΩrA; E 1 Ñ E 1 sq : E 1 Ď E is a cut between SJ and T u.

(10)

2. For all pα1 , ..., αN q P R0 pN , Aq and for all non-empty subset J Ď I we have
ÿ
αi ď min mintC0 pΩrA; E 1 Ñ E 1 sq : E 1 Ď E is a cut between SJ and T u.

(11)

iPJ

iPJ

T PT

T PT

Proof. We only show the two properties for J Ĺ I. The proof for the case J “ I is similar and easier.
Part 1 was essentially already shown in Subsection 6.1. More precisely, the bound in (10) follows
from (9) by minimizing over all T P T and E 1 .
Let us show part 2. Since the inequalities in p11q define a closed set in RN , it suffices to show
the result for R0 pN , Aq. Fix an arbitrary pα1 , ..., αN q P R0 pN , Aq. Let n ě 1, F 1 , ..., F n and
C “ C1 ˆ ¨ ¨ ¨ ˆ CN Ď X1n ˆ ¨ ¨ ¨ ˆ XNn be as in Definition 5.4.4. Take an element
˛n
˛n
¨
¨
ź
ź
ź
ź
Xi ‚ .
where we identify
Xin “ ˝
Xi ‚ ,
x “ px1 , ..., xn q P
Ci Ď ˝
iPIzJ

iPIzJ

iPIzJ

iPIzJ

Let T P T be a terminal, and let E 1 be a cut that separates SJ from T . To simplify the notation
throughout the proof, for all 1 ď k ď n define
ΩJF k rA; SJ Ñ T s :“ ΩJF k rA; SJ Ñ inpT q | xk s,
ΩJF k rSJ Ñ E 1 s :“ ΩJF k rSJ Ñ E 1 | xk s,

J

ΩJF k rE 1 Ñ T s :“ ΩJF k rE 1 Ñ inpT q | xk s,

ΩF k rA; SJ Ñ T s :“ ΩJF k rSJ Ñ E 1 s  ΩrA; E 1 Ñ E 1 s  ΩJF k rE 1 Ñ T s.

(12)

We can now apply Corollary 3.1.7 to equation (12), and obtain
˜
¸
˜
¸
n
n
n
ź
ź
ź
J
ΩF k rA; SJ Ñ T s “
ΩJF k rSJ Ñ E 1 s  ΩrA; E 1 Ñ E 1 sn 
ΩJF k rE 1 Ñ T s .
k“1

k“1

(13)

k“1

J

By assumption, we have ΩJF k rA; SJ Ñ T s ě ΩF k rA; SJ Ñ T s for all 1 ď k ď n. Combining this with
equation (13) we deduce
˜
¸
˜
¸
n
n
n
ź
ź
ź
J
J
1
1
1 n
J
1
ΩF k rA; SJ Ñ T s ě
ΩF k rSJ Ñ E s  ΩrA; E Ñ E s 
ΩF k rE Ñ T s .
k“1

k“1

k“1

śn

Since, byś
definition of R0 pN , Aq, the code C is good for k“1 ΩF k rA; S Ñ T s, the code
good for nk“1 ΩJF k rA; SJ Ñ T s. Thus by Proposition 3.1.5 we conclude that
ˇ
ˇ
ˇź ˇ 1 `
ÿ
˘
1
ˇ
ˇ
αi “ log|A| ˇ Ci ˇ ď C1 ΩrA; E 1 Ñ E 1 sn ď C0 pΩrA; E 1 Ñ E 1 sq.
ˇ
ˇ n
n
iPJ
iPJ
The final result can be obtained by minimizing over all T P T and E 1 .
23

ś

iPJ

Ci is

In the remainder of the section we establish an analogous porting lemma for the compound zeroerror capacity. We start by defining Hamming-type channels associated with an adversary of type
A “ At,e xU y.
Definition 6.2.2. Let L ě 1, U , t and e be as in Notation 5.3.3, and let V “ pV1 , ..., VL q Ď U be
arbitrary (possibly V “ U ). Take a non-empty subset of edges E 1 Ď E, and set s :“ |E 1 |. Denote by
e1 ă e2 ă ¨ ¨ ¨ ă es the edges in E, sorted according to the linear order extension ď. For all 1 ď ℓ ď L,
let Vℓ :“ t1 ď i ď s : ei P Uℓ u. The channel Ht,e xV, E 1 y is defined by Ht,e xV, E 1 y :“ Ht,e xV y : As 99K
Âs , where V :“ pV1 , ..., VL q and Ht,e xV y is the Hamming-type channel introduced in Definition 4.1.5.
The channel Ht,e xV, E 1 y can be interpreted as the “projection” of the adversary At,e xVy on E 1 . In
particular, note that E 1 determines the size of the input/output alphabets of the channel Ht,e xV, E 1 y.
We can now state the Compound Porting Lemma.
Lemma 6.2.3. Let U , t and e be as in Notation 5.3.3, and assume that A “ At,e xU y. Then for all
pα1 , ..., αN q P R0,cp pN , Aq and for all non-empty subset J Ď I we have
ÿ
αi ď min mintC0,cp pHt,e xU , E 1 yq : E 1 Ď E is a cut between SJ and T u.
iPJ

T PT

Sketch of the proof. We proceed as in the proof of Lemma 6.2.1. Take pα1 , ..., αN q P R0,cp pN , Aq, and
n and C “ C ˆ ¨ ¨ ¨ ˆ C Ď X n ˆ ¨ ¨ ¨ ˆ X n be as in Definition 5.4.7. Fix any element
let n ě 1, F 1 , ..., F ś
1
N
1
N
1
n
x “ px , ..., x q P iPIzJ Ci . Let T P T be a terminal, and let E 1 be a cut between SJ and T . To
simplify the notation throughout the proof, for V Ď U and for 1 ď k ď n we define
ΩJF k rAxVy; SJ Ñ T s :“ ΩJF k rAt,e xVy; SJ Ñ inpT q | xk s,
ΩJF k rSJ Ñ E 1 s :“ ΩJF k rSJ Ñ E 1 | xk s,

J

ΩJF k rE 1 Ñ T s :“ ΩJF k rE 1 Ñ inpT q | xk s,

ΩF k rAxVy; SJ Ñ T s :“ ΩJF k rSJ Ñ E 1 s  Ht,e xV, E 1 y  ΩJF k rE 1 Ñ T s.

(14)

J

Now observe that ΩJF k rAxVy; SJ Ñ T s ě ΩF k rAxVy; SJ Ñ T s for all 1 ď k ď n. Thus combining
equation (14), Corollary 3.1.7 and Proposition 3.2.2, we obtain
ď

n
ź

VĎU k“1
|V|ďt`e

ΩJF k rAxVy; SJ Ñ T s

ě

˜

n
ź

k“1

ΩJF k rSJ

1

¸

ÑEs

¨

˚ ď
˚
˝

VĎU
|V|ďt`e

˛

1 n‹

‹
Ht,e xV, E y ‚

˜

n
ź

k“1

ΩJF k rE 1

As in the proof of Lemma 6.2.1, by Proposition 3.1.5 we conclude
¨
˛
ˇ
ˇ
ˇź ˇ 1 ˚ ď
ÿ
‹
1
ˇ
ˇ
1
αi “ log|A| ˇ Ci ˇ ď C1 ˚
Ht,e xV, E 1 yn ‹
˝
‚ ď C0,cp pHt,e xU , E yq,
ˇ
ˇ n
n
iPJ
iPJ
VĎU

Ñ Ts .

|V|ďt`e

where the last inequality can be shown using the definition of Ht,e xV, E 1 y (see Definition 6.2.2).

24

¸

7

Capacity Regions: Upper Bounds

In this section we apply the theoretical bounds established in Section 6 to concrete networking contexts.
Our results study one-shot models, zero-error models, and compound zero-error models. Moreover,
they cover several classes of network adversaries, including multiple adversaries, restricted adversaries,
different types of error/erasure adversaries, and rank-metric adversaries (see Section 9). The bounds
presented in this section do not follow in any obvious from known results in the context of network
communications under probabilistic error models.
We follow the notation of Section 5, and work with a fixed network N “ pV, E, S, Tq over an
alphabet A. The network sources are S “ tS1 , ..., SN u, and I “ t1, ..., N u is the set of source indices.
We let β be the parameter introduced in Notation 4.1.1.
Notation 7.0.1. If J Ď I is a non-empty subset and T P T is a terminal, we denote by µpSJ , T q
the min-cut between SJ and T , i.e., the minimum size of an edge-cut that separates all the sources
in SJ from T . By the edge-connectivity version of Menger’s Theorem (see [31]), µpSJ , T q coincides
with the maximum number of edge-disjoint directed paths connecting SJ to T . Note moreover that,
by property (E) of Definition 5.1.1, one has µpSJ , T q ě 1 for all non-empty J Ď I and for all T P T.

7.1

One-Shot Capacity Region

We start by considering a single adversary A restricted to a set of edges U Ď E, with limited error and
erasure powers. The following result shows that any bound from classical Coding Theory translates
into a bound for the one-shot capacity region of pN , Aq via the Porting Lemma.
Theorem 7.1.1. Let U Ď E be a subset of edges, and let t, e ě 0 be integers. Assume A “ At,e xU y.
For all pα1 , ..., αN q P RpN , Aq and for all non-empty J Ď I we have
ÿ
(
αi ď min min |E 1 zU | ` βpA, |E 1 X U |, 2t ` e ` 1q : E 1 Ď E is a cut between SJ and T .
(15)
iPJ

T PT

In particular, if U “ E then for all pα1 , ..., αN q P RpN , Aq and for all non-empty J Ď I we have
ÿ
αi ď min βpA, µpSJ , T q, 2t ` e ` 1q.
iPJ

T PT

Proof. Combine Proposition 4.1.4 and part 1 of Lemma 6.2.1. The second part of the statement
follows from the fact that βpA, u1 , 2t ` e ` 1q ď βpA, u, 2t ` e ` 1q for all u ě u1 ě 1.
Remark 7.1.2. When U Ĺ E in Theorem 7.1.1, the second minimum in (15) is not realized, in
general, by a minimum cut E 1 between SJ and T (examples can be easily found). Thus the topology
of the set U of “vulnerable” edges plays an important role in the evaluation of the bound in (15).
As special cases of Theorem 7.1.1, we obtain generalizations of the Singleton-type and Hammingtype bounds established in [2] for single-source networks. Note that any other classical bound from
Coding Theory can be ported to the networking context via Theorem 7.1.1, in the general case where
the adversary is possibly restricted to operate on a subset U Ď E of vulnerable edges. Observe moreover
that no extra property of the edge-cuts E 1 is needed in Theorem 7.1.1. In particular, we do not require
that the sets E 1 are antichain cuts (see also Remark 5.2.4).
Corollary 7.1.3 (Singleton-type and Hamming-type bound). Let t, e ě 0 be integers, and assume
A “ At,e xEy. Then for all pα1 , ..., αN q P RpN , Aq and for all non-empty J Ď I we have
ÿ
αi ď min max t0, µpSJ , T q ´ 2t ´ eu
iPJ

T PT

25

and
ÿ

iPJ

$
¨ 1
˛,
˙
t ˆ
&
.
ÿ
µpSJ , T q
αi ď min max 0, µpSJ , T q ´ log|A| ˝
p|A| ´ 1qh ‚ ,
%
T PT
h
h“0

where t1 :“ tt ` e{2u.

Proof. The result can be shown by combining Theorem 7.1.1 and the well known Singleton bound and
Hamming bound from classical Coding Theory (see [32] for a general reference). Note that the proofs
of these two bounds do not require the alphabet A to be a finite field.
Example 7.1.4. Let N be the network in Figure 8. The edges are ordered according to their indices.
Consider the adversary A :“ A1,0 xEy who can corrupt at most one of the values of the edges from E.
Let A be the network alphabet, and let pα1 , α2 q P RpN , Aq be arbitrary.
e1
e2

S1

V1
e7
e8

e3

T
e9
e 10

e4
e5
e6

S2

V2

Figure 8: Network for Example 7.1.4.
Using the Singleton-Type bound of Corollary 7.1.3 with I “ t1u we get α1 ď 1. Applying the
same bound with I “ t2u and I “ t1, 2u one obtains, respectively, α2 ď 1 and α1 ` α2 ď 2. Therefore
RpN , Aq Ď tpα1 , α2 q P R2ě0 : α1 ď 1, α2 ď 1, α1 ` α2 ď 2u for any alphabet A.
Now assume A “ F2 . Applying in the same way the Hamming-Type bound we obtain
RpN , Aq Ď tpα1 , α2 q P R2ě0 : α1 ď 1, α2 ď 1, α1 ` α2 ď 4 ´ log2 5u

for A “ F2 .

(16)

Using the definition of one-shot capacity region (Definition 5.4.2), it is easy to see that (16) implies
that RpN , Aq Ď tp0, 0q, p1, 0q, p0, 1qu for A “ F2 . Therefore for A “ F2 the Hamming-Type Bound is
better than the Singleton-type Bound.

7.2

Other Capacity Regions

We now consider multiple adversaries acting on pairwise disjoint sets of network edges, with different
error and erasure powers. In this context, the three capacity regions defined in Subsection 5.4 can be
upper-bounded by combining the Compound Porting Lemma with the results established in Section 4.
Theorem 7.2.1. Fix an integer L ě 1. Let U1 , ..., UL Ď E be pairwise disjoint subsets of edges, and
let t1 , ..., tL ě 0 and e1 , ..., eL ě 0 be non-negative integers. Define U :“ pU1 , ..., UL q, t :“ pt1 , ..., tL q
and e :“ pe1 , ..., eL q, and assume A “ At,e xU y. Then for all pα1 , ..., αN q P R0,cp pN , Aq and for all
non-empty subset J Ď I we have
#
+
L
ÿ
ÿ
(
αi ď min min |E 1 | ´
min 2tℓ ` eℓ , |E 1 X Uℓ | : E 1 Ď E is a cut between SJ and T . (17)
iPJ

T PT

ℓ“1

In particular, the inequality in (17) holds for all non-empty J Ď I and for any pα1 , ..., αN q P R0 pN , Aq
and pα1 , ..., αN q P RpN , Aq.
26

Proof. It suffices to combine Theorem 4.3.1 and Lemma 6.2.3. The second part of the statement
follows from the fact that RpN , Aq Ď R0 pN , Aq Ď R0,cp pN , Aq, as observed in Remark 5.4.8.
We now show how to apply Theorem 7.2.1 in a concrete example.
Example 7.2.2. Let N be the network in Figure 9. The network edges are ordered according to
their indices. We consider two adversaries associated with the sets of edges U1 “ te5 , e6 , e7 u and
U2 “ te1 , e8 , e9 , e10 , e11 , e12 u. Both the adversaries have error power 1 and erasure power 0. In our
notation, the adversary is therefore A “ At,e xU y, where U “ pU1 , U2 q, t “ p1, 1q and e “ p0, 0q.
S1

e1

V1

e2

e8

e1

e3

e9

e4

0

T

S2

e6

e5
e7

V2

e 11
e 12

Figure 9: Network for Example 7.2.2.
We want to describe the three capacity regions of pN , Aq. Let pα1 , ..., αN q P R0,cp pN , Aq be
arbitrary. Applying Theorem 7.2.1 with I “ t1u and E 1 “ te1 , e2 u we obtain α1 ď 2 ´ 1 “ 1. Using
the same theorem with I “ t2u and E 1 “ te5 , e6 , e7 , e8 , e9 , e10 u we find α2 ď 6 ´ 2 ´ 2 “ 2. Finally,
applying again Theorem 7.2.1 with I “ t1, 2u and E 1 “ te2 , e5 , e6 , e7 , e8 , e9 , e10 u we obtain α1 ` α2 ď 3.
Therefore by Remark 5.4.8 we deduce
RpN , Aq Ď R0 pN , Aq Ď R0,cp pN , Aq Ď tpα1 , α2 q P R2ě0 : α1 ď 1, α2 ď 2, α1 ` α2 ď 3u.
We now explicitly give a communication scheme that achieves the rate pα1 , α2 q “ p1, 2q in one shot
for A “ F5 . It can be shown that such a scheme exists for A “ Fq whenever q ě 4.
We start by assigning the network code functions. Since erasures are excluded from the model,
it suffices to assign functions FV1 : F35 Ñ F35 and FV2 : F45 Ñ F25 . For all px1 , x3 , x4 q P F35 , define
FV1 px1 , x3 , x4 q :“ px1 ` 2x3 ` 3x4 , x3 , x4 q. To define F2 , we first select any function f : F35 Ñ F5 with
the following property: for all px5 , x6 , x7 q P F35 and x P F5 , f px5 , x6 , x7 q “ x if at least two among
x5 , x6 , x7 equal x. The function f is an arbitrary extension of a “majority vote” decoding function.
Now for all px2 , x5 , x6 , x7 q P F45 define FV2 px2 , x5 , x6 , x7 q :“ px2 ` f px5 , x6 , x7 q, 2x2 q.
Let us construct the local codes C1 Ď F25 and C2 Ď F55 for the two sources S1 and S2 . We take
C1 :“ tpa, 3aq : a P F5 u as code for source S1 , and C2 :“ tpb, c, 2b ` c, 2b ` c, 2b ` cq : pb, cq P F5 ˆ F5 u
as code for source S2 . Note that log5 |C1 | “ 1 “ α1 and log5 |C2 | “ 2 “ α2 .
It is easy to see that for any transmitted pa, 3aq P C1 and pb, c, 2b ` c, 2b ` c, 2b ` cq P C2 , terminal
T observes over the incoming edges the vector
pa ` 2b ` 3c, b, c, 3a ` 2b ` c, aq ` w,
where w P F55 is a vector of Hamming weight at most 1. Note moreover that
˛
¨
1 0 0 3 1
pa ` 2b ` 3c, b, c, 3a ` 2b ` c, aq “ pa, b, cq ¨ G,
where G :“ ˝2 1 0 2 0‚ P F53ˆ5 .
3 0 1 1 0

(18)

One can check that G is the generator matrix of a code D Ď F55 of dimension 3 and minimum Hamming
distance 3. Thus T can recover a, b and c from (18) using a minimum distance decoder for D.
27

Theorem 7.2.1 implies the following corollary describing special types of adversaries.
Corollary 7.2.3. Let t ě 0 be an integer, and assume A “ At,0 xEy. For all pα1 , ..., αN q P R0,cp pN , Aq
and for all non-empty J Ď I we have
ÿ
αi ď min max t0, µpSJ , T q ´ 2tu .
iPJ

T PT

In particular, if N is adversary-free then for all pα1 , ..., αN q P R0,cp pN , Aq and all H ‰ J Ď I we have
ÿ
αi ď min µpSJ , T q.
iPJ

T PT

Moreover, the two bounds above hold for all non-empty J Ď I and for any pα1 , ..., αN q P R0 pN , Aq
and pα1 , ..., αN q P RpN , Aq.
We conclude this section studying the scenario where the network alphabet is of the form A “ B m ,
where B is a finite set with |B| ě 2 and m ě 2 is an integer. Consider an adversary A who can erase
up to e components and corrupt up to t components of each edge of the network, where t, e ě 0 are
non-negative integers. We denote such an adversary by At,e xB, my. Combining Theorem 4.4.3 and
Lemma 6.2.1 one easily obtains the following result.
Theorem 7.2.4. Let t, e ě 0 be non-negative integers, and assume A “ At,e xB, my. Then for all
pα1 , ..., αN q P R0 pN , Aq and for all non-empty subset J Ď I we have
ÿ
m¨
αi ď min µpSJ , T q ¨ maxt0, m ´ 2t ´ eu.
(19)
iPJ

T PT

In particular, the inequality in (19) holds for all non-empty J Ď I and for all pα1 , ..., αN q P RpN , Aq.

8

Capacity Regions: Constructions

This section studies the achievability of some of the upper bounds established in Section 7, both for
one-shot and (compound) zero-error models. We describe communication schemes that achieve any
integer point of the capacity region of certain adversarial networks, most of which are inspired by
previously proposed approaches (in particular, by [23] and [25]). We also show that, for the case of
restricted adversaries, linear network coding does not suffice in general to achieve every point in the
capacity region of adversarial networks. In the sequel we follow the notation of Section 7.

8.1

Adversary-Free Scenario

We start by investigating the adversary-free scenario, showing how in this case the algebraic approach
of [25] can be extended to achieve, in one shot, any integer point in the rate region described by the
bound of Corollary 7.2.3, over sufficiently large fields.
ř
Remark 8.1.1. Let pa1 , ..., aN q P NN be an integer vector that satisfies iPJ ai ď minT PT µpSJ , T q
for all H ‰ J Ď I (cf. Corollary 7.2.3). To show that pa1 , ..., aN q can be achieved in one shot in
an adversary-free context, it does not suffice to directly apply the approach of [25] to the network
obtained from N by adding a super-source connected to all the sources S1 , ..., SN with a sufficiently
large number of edges. Indeed, this approach would only show that there exists a communication
scheme that allows the set of sources tS1 , ..., SN u to transmit to all the terminals at a global rate of
a1 ` a2 ` ¨ ¨ ¨ ` aN . However, such a scheme does not necessarily allow each source Si to transmit at
the prescribed rate ai , for all i P I. In other words, in the notation of Definition 5.4.2, such a scheme
28

does not necessarily induce a global code C for the sources that decomposes as a cartesian product,
defining local codes C1 , ..., CN . This issue can be solved by extending the algebraic approach of [25] to
multi-source networks via the following Graph Theory lemma.
ř
Lemma 8.1.2. Let pa1 , ..., aN q P NN be an integer N -tuple such that iPJ ai ď minT PT µpSJ , T q for
all non-empty J Ď I. Then for each terminal T P T there exist a1 ` a2 ` ¨ ¨ ¨ ` aN edge-disjoint directed
paths connecting S “ tS1 , ..., SN u to T , ai of which originate in Si for all i P I.
Proof. We start by adding a vertex S R V to the digraph G :“ pV, Eq. For all i P I, connect S to Si
with exactly ai directed edges. This defines a new digraph G 1 :“ pV 1 , E 1 q. Fix any terminal T P T. By
the edge-connectivity version of Menger’s Theorem, it suffices to show that the minimum size of an
edge-cut between S and T (in the graph G 1 ) is a :“ a1 ` a2 ` ¨ ¨ ¨ ` aN , i.e., that µpS, T q “ a, where
this time µ denotes the min-cut in the new graph G 1 .
It is clear that µpS, T q ď a. Assume by contradiction that there exists a cut Γ Ď E 1 with |Γ| ă a
that separates S from T . For all i P I “ t1, ..., N u, denote by Ei the set of directed edges connecting
S to Si , and let ni :“ |Γ X Ei |. Since Ei X Ej “ H for all i, j P I with i ‰ j, we have
ÿ
ÿ
ÿ
ni “
|Γ X Ei | ď |Γ| ă a “
ai .
(20)
iPI

iPI

iPI

Moreover, for all i P I one clearly has ni “ |Γ X Ei | ď |Ei | “ ai . Define J :“ ti P I : ni ă ai u Ď I.
If J “ H then ai “ ni for all i P I. This contradicts (20). Now assume J ‰ H, and observe that
for all i P J the cut Γ doesŤnot disconnect S from Si . Hence Γ must be a cut between SJ and T . As
a consequence, the set Γz iPIzJ Ei is a cut between SJ and T . Therefore
ˇ
ˇ
ˇ
ď ˇˇ
ÿ
ÿ
ÿ
ÿ
ˇ
µpSJ , T q ď ˇˇΓz
Ei ˇˇ “ |Γ| ´
ni “ |Γ| ´
ai ă a ´
ai “
ai ,
ˇ iPIzJ ˇ
iPJ
iPIzJ
iPIzJ
iPIzJ

a contradiction. This concludes the proof.

Lemma 8.1.2 can now be employed to extend the approach of [25] from one to multiple sources,
obtaining the following achievability result for adversary-free networks.
Theorem 8.1.3. Assume A “ A0,0 xEy. We have
#
+
ÿ
RpN , Aq Ě pa1 , ..., aN q P NN :
ai ď min µpSJ , T q for all H ‰ J Ď I ,
T PT

iPJ

provided that A “ Fq and q is sufficiently large. Moreover, every integer rate vector pa1 , ..., aN q as
above can be achieved in one shot employing linear network coding.
ř
Proof. Let pa1 , ..., aN q P NN be an integer vector such that iPJ ai ď minT PT µpSJ , T q for all H ‰ J Ď
I. By Lemma 8.1.2, for each terminal T P T there exist a1 ` ¨ ¨ ¨ ` aN edge-disjoint paths connecting
S to T , of which ai originate in Si for all i P I. Without loss of generality, we may assume that there
is neither an edge nor a vertex of N which is not on at least one of these |T| ¨ pa1 ` ¨ ¨ ¨ ` aN q paths.
In particular, source Si has at least ai outgoing edges for all i P I, and every terminal T has exactly
a :“ a1 ` ¨ ¨ ¨ ` aN incoming edges (we are using property (F) of Definition 5.1.1).
For all i P I, we let the local code of source Si to be of the form Ci :“ tv ¨ Ei : v P Faq i u, where Ei
is a matrix of size ai ˆ |outpSi q| over Fq to be determined.
Since erasures are excluded from the model, to construct a linear network code F for N it suffices
to assign an p|inpV q| ˆ |outpV q|q-matrix FV over Fq for every V P VzpS Y Tq. See Definition 5.2.1.
29

In analogy with [25], we introduce a variable for each entry of each of the matrices Ei and FV ,
for i P I and V P VzpS Y Tq. We denote these variables by ζ1 , ..., ζM , and let ζ :“ pζ1 , ..., ζM q. In
the sequel, the Ei ’s and FV ’s are denoted by Ei pζq and FV pζq, to stress the dependency on ζ. An
evaluation ζ “ pζ 1 , ..., ζ M q P FM
q of the variables induces matrices Ei pζq, for i P I, and a linear network
code Fpζq for N . Moreover, for all T P T and for all px1 , ..., xN q P Faq 1 ˆ ¨ ¨ ¨ ˆ Faq N we have
ΩF pζq rS Ñ inpT qspx1 ¨ E1 pζq, ..., xN ¨ EN pζqq “ px1 , ..., xN q ¨ MT pζq
for some a ˆ a transfer matrix MT pζq whose entries are polynomials in ζ1 , ..., ζM evaluated in ζ. Note
that the matrix MT pζq has size a ˆ a by property (F) of Definition 5.1.1.
By definition of one-shot capacity region, to prove the theorem it suffices to show that, for a
large enough q, there exists an evaluation ζ of the variables such that each matrix MT pζq, T P T, is
invertible. As in [25], this fact follows from the Sparse Zeros Lemma (see, e.g., [33, Lemma 1]) and
the existence of the routing solutions. The details of this part of the argument are left to the reader.
The invertibility of the MT pζq’s implies that each Ei pζq, i P I, is injective as a linear map.
This shows that log|A| |Ci | “ ai for all i P I, defining local codes for the sources of the expected
cardinalities.

8.2

Single Error-Adversary With Access to All Edges

In this subsection we focus on adversaries of the form A “ At,0 xEy, and show that every integer vector
pa1 , ..., aN q P NN in the region described by Corollary 7.2.3 can be achieved in one shot, provided that
A “ Fm
q , and that q and m are sufficiently large. Our scheme is a simple modification of an idea
from [23], in which the authors propose a scheme in the context of random linear network coding.
Note that the following Theorem 8.2.1 cannot be directly obtained from classical results in the
context of network communications under probabilistic error/erasure models.
Theorem 8.2.1. Let t ě 0 be an integer, and assume A “ At,0 xEy. We have
#
+
ÿ
N
RpN , Aq Ě pa1 , ..., aN q P N :
ai ď min max t0, µpSJ , T q ´ 2tu for all H ‰ J Ď I ,
iPJ

T PT

ś
provided that A “ Fm
q , q is sufficiently large, and m “
iPI pai ` 2tq. Moreover, every integer rate
vector pa1 , ..., aN q as above can be achieved in one shot employing linear network coding.
Proof. We will show the theorem only for N “ 2 sources and in the case where, for any terminal
T P T, we have µpS1 , T q, µpS2 , T q, µpS, T q ą 2t.
Fix a pair pa1 , a2 q P N2 with a1 ď µpS1 , T q´ 2t, a2 ď µpS2 , T q´ 2t and a1 ` a2 ď µpS, T q´ 2t for all
T P T. Observe that a1 ď µpS1 , T q, a2 ` 2t ď µpS2 , T q, and a1 ` pa2 ` 2tq ď µpS, T q. By Lemma 8.1.2,
for each T P T there exist a1 ` a2 ` 2t edge-disjoint paths connecting S to T , of which a1 originate in
S1 , and a2 ` 2t originate in S2 . Moreover, as a1 ` 2t ď µpS1 , T q, there exist a1 ` 2t edge-disjoint paths
connecting S1 to T . Without loss of generality, we may assume that there is neither an edge nor a
vertex of N which is not on at least one of these |T| ¨ pa1 ` a2 ` 2t ` a1 ` 2tq “ |T| ¨ p2a1 ` a2 ` 4tq
paths. Finally, for ease of notation define:
n1 :“ a1 ` 2t,

n2 :“ a2 ` 2t,

q1 :“ q n1 ,

q2 :“ q1n2 ,

b1 :“ |outpS1 q|,

b2 :“ |outpS2 q|.

Before describing a communication scheme that achieves pa1 , a2 q in one shot, following [23] we
introduce some maps needed in the sequel. Fix finite fields Fq Ď Fq1 Ď Fq2 and bases tβ11 , ..., β1n1 u,
tβ21 , ..., β2n2 u for Fq1 and Fq2 over Fq and Fq1 , respectively. We denote by ϕ1 : Fq1 Ñ Fnq 1ˆ1 the
Fq -isomorphism that expands an element of Fq1 over the basis tβ11 , ..., β1n1 u. Similarly, we denote by
30

ϕ2 : Fq2 Ñ Fnq12 ˆ1 the Fq1 -isomorphism that expands an element of Fq2 over the basis tβ21 , ..., β2n2 u.
Extend the maps ϕ1 and ϕ2 entry-wise to matrices or arbitrary size over Fq1 and Fq2 , respectively.
Note that the entries of matrices are always expanded as column vectors.
We now describe the communication scheme. Set m :“ n1 n2 , so that A “ Fqn1n2 is the alphabet.
Let G1 P Faq11 ˆn1 be the generator matrix of a rank-metric code D1 Ď Fnq11 with dimFq1 pD1 q “ a1 and
minimum rank distance 2t ` 1 over Fq (see [34]). Similarly, let G2 P Faq22 ˆn2 be the generator matrix
of a rank-metric code D2 Ď Fnq22 with dimFq2 pD2 q “ a2 and minimum rank distance 2t ` 1 over Fq1 .
Source S1 chooses an arbitrary matrix X1 P Fqn12 ˆa1 , computes X1 G1 P Fnq12 ˆn1 , and sends over
the outgoing edges the columns of the matrix ϕ1 pX1 G1 qE1 P Fnq 1 n2 ˆb1 , where E1 P Fnq 1 ˆb1 is a local
2 , computes X G
encoding matrix to be determined. Source S2 chooses an arbitrary X2 P F1ˆa
2 2 P
q2
1ˆn
Fq2 2 , and sends over the outgoing edges the columns of the matrix ϕ1 pϕ2 pX2 G2 qqE2 P Fnq 1 n2 ˆb2 ,
where E2 P Fnq 2 ˆb2 is another local encoding matrix that will be chosen later in the proof.
The vertices in VzpS Y Tq process the incoming packets using a linear network code F. According
to Definition 5.2.1, we therefore need to assign to every V P VzpS Y Tq an |inpV q| ˆ |outpV q| matrix
FV over Fq (erasures are excluded from the model).
As in the proof of Theorem 8.1.3, we introduce a variable for each entry of each of the matrices
Ei and FV , for i P t1, 2u and V P VzpS Y Tq. We denote these variables by ζ1 , ..., ζM , and let
ζ :“ pζ1 , ..., ζM q. In the sequel, the Ei ’s and FV ’s are denoted by Ei pζq and FV pζq. Note that an
evaluation ζ “ pζ 1 , ..., ζ M q P FM
q of the variables induces matrices Ei pζq, for i P t1, 2u, and a linear
2 we have
network code Fpζq for N . Moreover, for all T P T and for all X1 P Fqn12 ˆa1 and X2 P F1ˆa
q2
ΩF pζq rS Ñ inpT qspϕ1 pX1 G1 qE1 pζq, ϕ1 pϕ2 pX2 G2 qqE2 pζqq

“ ϕ1 pX1 G1 qE1 pζq ¨ MT1 pζq ` ϕ1 pϕ2 pX2 G2 qqE2 pζq ¨ MT2 pζq,

where the packets are organized as column vectors, and MT1 pζq, MT2 pζq are the transfer matrices from
source S1 and S2 , respectively, to the terminal T . These two matrices are well defined in the context
of erasure-free linear network coding (see [23, Section VII.B]), and their entries are polynomials in
ζ1 , ..., ζM evaluated in ζ. Note that the size of MTi pζq is bi ˆ |inpT q|, for all T P T and i P t1, 2u.
Using the existence of routing solutions and the Sparse Zeros Lemma (e.g., [33, Lemma 1]), it can
be shown that there exists an evaluation ζ P FM
q of the variables such that, for all T P T, the matrices
AT pζq :“

ˆ

G1 E1 pζqMT1 pζq
E2 pζqMT2 pζq

˙

P Fqpa11 `n2 qˆ|inpT q| ,

˘
`
BT pζq :“ E1 pζqMT1 pζq P Fqn1 ˆ|inpT q|

(21)

are both right-invertible (or equivalently full-rank), provided that q is sufficiently large (for details
about the matrix AT pζq, see the proof of [23, Lemma 2]). In the sequel we fix such an evaluation ζ,
and simply write E1 , E2 , F, MT1 , MT2 , AT , BT for E1 pζq, E2 pζq, Fpζq, MT1 pζq, MT2 pζq, AT pζq, BT pζq.
The local codes for sources S1 and S2 are, respectively,
C1 “ tϕ1 pX1 G1 qE1 : X1 P Fqn11 ˆa1 u Ď Fqn1 n2 ˆb1 ,

2
C2 “ tϕ1 pϕ2 pX2 G2 qqE2 : X2 P F1ˆa
u Ď Fnq 1 n2 ˆb2 ,
q2

where the network packets are again organized as column vectors. Since the matrices in (21) are both
full-rank, the matrices E1 and E2 are full-rank as well (and thus right-invertible). As a consequence,
2 | “ q ma2 . Therefore it remains to prove that C ˆ C
we have |C1 | “ |Fnq12 ˆa1 | “ q ma1 and |C2 | “ |F1ˆa
1
2
q2
is good for each channel ΩF rA; S Ñ inpT qs, T P T. We will show this by explicitly giving a decoding
procedure. In the remainder of the proof the packets will be always organized as column vectors.
A given terminal T P T receives
RT “ ϕ1 pX1 G1 qE1 MT1 ` ϕ1 pϕ2 pX2 G2 qqE2 MT2 ` ZT P Fnq 1 n2 ˆ|inpT q| ,
31

(22)

where Z is an error matrix such that rkFq pZT q ď t (see [15, Section IV] for details). Applying ϕ´1
1 to
both sides of (22), and using the fact that such map is Fq -linear, the terminal computes
`
˘
1
2
´1
´1
ϕ´1
1 pRT qX1 G1 E1 MT ` ϕ2 pX2 G2 qE2 MT ` ϕ1 pZT q “ X1 ϕ2 pX2 G2 q AT ` ϕ1 pZT q.
Terminal T can now multiply on the right both members of the previous equality by the right-inverse
of AT , which is a matrix over Fq1 denoted by A´1
T , and obtain
`
˘
´1
´1
´1
(23)
ϕ´1
1 pRT qAT “ X1 ϕ2 pX2 G2 q ` ϕ1 pZT qAT .

´1
´1
Observe that rkFq1 pϕ´1
1 pZT qAT q ď rkFq1 pϕ1 pZT qq ď rkFq pZT q ď t, where the second inequality
2
follows from [23, Lemma 1]. Therefore T can delete the first a1 columns of (23), and recover X2 P F1ˆa
q2
using a minimum rank-distance decoder for the code generated by G2 . Now T uses (22) and computes

RT :“ RT ´ ϕ1 pϕ2 pX2 G2 qqE2 MT2 “ ϕ1 pX1 G1 qE1 MT1 ` ZT “ ϕ1 pX1 G1 qBT ` ZT .

(24)

By our choice of ζ, BT is a right-invertible matrix over Fq , whose right-inverse is denoted by BT´1 .
Multiplying on the right both sides of (24) by BT´1 , the terminal obtains
RT BT´1 “ ϕ1 pX1 G1 q ` ZT BT´1 P Fnq 1 n2 ˆn1 .

(25)

Define X :“ ϕ1 pX1 G1 q and Z T :“ ZT BT´1 . Organize the n1 n2 rows of X and Z T in n2 blocks of n1
rows, and re-write (25) as
¨ 1˛ ¨ 1˛
X
ZT
˚
‹ ˚
‹
RT BT´1 “ X ` Z T “ ˝ ... ‚` ˝ ... ‚.
X

i

n2

n

Z T2

i

Since rkFq pZT q ď t, we have rkFq pZ T q ď t for all 1 ď i ď n2 . Moreover, ϕ1 , X “ ϕ1 pX1i G1 q, where
X1i is the i-th row of X1 . Therefore T can recover X by applying n2 times a minimum rank-distance
decoder for the code generated by G1 . Clearly, this allows T to recover X1 as well.

8.3

A Scheme for the Compound Model

In this subsection we adapt the scheme of Theorem 8.2.1 to the compound model, i.e., to the scenario
where the adversary is forced to act on the same set of edges in each network use. We show that,
in this specific context, the use of long network packets can be avoided by employing the network
multiple times. Note that this fact does not follow directly from Theorem 8.2.1, as a network alphabet
of the form Fm
q does not model m uses of the network (see Remark 5.4.5). In fact, our scheme does
not work if the adversary can act on a different set of edges in each channel use.
Theorem 8.3.1. Let t ě 0 be an integer, and assume A “ At,0 xEy. We have
#
+
ÿ
N
R0,cp pN , Aq Ě pa1 , ..., aN q P N :
ai ď min max t0, µpSJ , T q ´ 2tu for all H ‰ J Ď I ,
iPJ

T PT

provided that A “ Fm
q , q is sufficiently large, and m :“ mintai : i P I, ai ‰ 0u ` 2t. Moreover, every
integer rate vector pa1 , ..., aN q as above can be achieved using linear network coding.
Proof. As for Theorem 8.2.1, we show the result only for N “ 2 sources and in the case where, for
any T P T, we have µpS1 , T q, µpS2 , T q, µpS, T q ą 2t. Assume a1 ď a2 without loss of generality.
In the sequel we follow the notation of the proof of Theorem 8.2.1, and modify the scheme to
achieve pa1 , a2 q in n2 channel uses, provided that A “ Fnq 1 and q is sufficiently large. In every network
32

use, each intermediate vertex V P VzpS Y Tq processes the incoming packets according to the network
code F constructed in the proof of Theorem 8.2.1 (thus F is the same in every network use).
After choosing X1 and X2 , sources S1 and S2 compute ϕ1 pX1 G1 q, ϕ1 pϕ2 pX2 G2 qq P Fnq 1 n2 ˆn1 ,
respectively. The rows of these matrices are then organized in n2 blocks of n1 rows:
¨ 1˛
¨ 1˛
Y2
Y1
˚ .. ‹
˚ .. ‹
ϕ1 pX1 G1 q “ ˝ . ‚, ϕ1 pϕ2 pX2 G2 qq “ ˝ . ‚.
Y2n2

Y1n2

In the j-th network use, Si sends over the outgoing edges the columns of Y1j Ei P Fnq 1 ˆbi , for 1 ď j ď n2
and i P t1, 2u. This defines codes C1 , C2 for S1 and S2 of cardinality q n1 n2 a1 and q n1 n2 a2 , respectively.
The decoding is as follows. In the j-th network use, terminal T P T collects packets from Fnq 1
over the incoming edges, and organizes them as the columns of a n1 ˆ |inpT q| matrix over Fq , which is
denoted by RTj . Observe that RTj “ Y1j E1 MT1 ` Y2j E2 MT2 ` ZTj , where ZTj is the error matrix. Recall
n ˆ|E|
that ZTj is defined by ZTj :“ W j UT , where W j P Fq 1
is the matrix whose columns are the error
packets, and UT is the |E| ˆ |inpT q| transfer matrix from the edges of N to the destination T . Note
that UT is well defined in the context of erasure-free linear network coding (see [15, Section I and IV]
for details). After n2 channel uses, terminal T constructs the matrix
¨ 1˛
¨ 1˛
RT
ZT
˚ .. ‹
˚ .. ‹
1
2
RT :“ ˝ . ‚ “ ϕ1 pX1 G1 qE1 MT ` ϕ1 pϕ2 pX2 G2 qqE2 MT ` ZT , where ZT :“ ˝ . ‚.
(26)
RTn2

ZTn2

Now observe that ZT can be written as
¨ 1˛
ZT
˚ .. ‹
ZT “ ˝ . ‚ “ W UT ,
ZTn2

˛
W1
˚ .. ‹
˝ . ‚ P Fnq 1 n2 ˆ|E| .
¨

W n2

Since the adversary acts on the same edges in each network use, the matrix W has at most t non-zero
columns, which implies rkFq pZT q ď rkFq pW q ď t (this fact would not be true if the adversary was able
to act on a different set of edges in each use of the channel). Decoding can therefore be completed
starting from equation (26) as in the proof of Theorem 8.2.1 (cf. equation (22)).

8.4

Product Network Alphabets

Throughout this subsection we assume that A “ B m is a product alphabet, where B is a finite set with
|B| ě 2 and m ě 2 is a fixed integer. The following theorem describes a capacity-achieving scheme for
adversarial networks of the form pN , Aq, where A “ At,e xB, my is the adversary of Theorem 7.2.4.
Theorem 8.4.1. Let t, e ě 0 be integers, and let A “ At,e xB, my. Assume m ě 2t ` e ` 1, and let
k :“ m ´ 2t ´ e. Then
+
#
ÿ
k
N
pa1 , ..., aN q P Rě0 : ai P N for all i P I,
ai ď min µpSJ , T q for all H ‰ J Ď I ,
RpN , Aq Ě
T PT
m
iPJ
provided that B “ Fq and q is sufficiently large.
ř
Proof. Let pa1 , ..., aN q P NN be an integer vector such that iPJ ai ď minT PT µpSJ , T q for all nonempty J Ď I. By Lemma 8.1.2, for each terminal T P T there exist a1 ` ¨ ¨ ¨ ` aN edge-disjoint paths
connecting S to T , of which ai originate in Si for all i P I. Without loss of generality, we may assume
33

that there is neither an edge nor a vertex of N which is not on at least one of these paths. Moreover,
we let Ei pζq and FV pζq, for i P I and V P VzpS Y Tq, be as in the proof of Theorem 8.1.3.
We will give a communication scheme (and therefore construct a pair pF, Cq) that achieves the
k
rate k{m ¨ pa1 , ..., aN q in one shot. Let D Ď Fm
q be a code of cardinality q and minimum Hamming
m
k
distance d “ 2t ` e ` 1. Let Enc : Fkq Ñ Fm
q and Dec : pFq Y t‹uq Ñ Fq be an encoder and a decoder
for D, respectively. For all i P I, let bi :“ |outpSi q|. Source Si chooses xi “ pxi,1 , ..., xi,ai q P pFkq qai ,
computes
` J
˘
˘
` J
kˆbi
J
xi,1 ¨ ¨ ¨ xJ
,
i,ai ¨ Ei pζq “: yi,1 ¨ ¨ ¨ yi,bi P Fq
and sends Encpyi,1 q, ..., Encpyi,bi q P Fm
q over the outgoing edges. Since the Ei pζq’s are injective as
linear maps (see the proof of Theorem 8.1.3), this defines local codes C1 , ..., CN for the sources with
kai “ k{m ¨ a , for all i P I.
bi
Ci Ď pFm
i
q q and log |A| |Ci | “ log q m q
Let V P VzpS Y Tq be a vertex, and set r :“ |inpV q|, s :“ |outpV q| for ease of notation. The vertex
V collects x1 , ..., xr P pFq Y t‹uqm over the incoming edges, and computes
`
˘
`
˘
.
Decpx1 qJ ¨ ¨ ¨ Decpxr qJ ¨ FV pζq “: y1J ¨ ¨ ¨ ysJ P Fmˆd
q

The vectors Encpy1 q, ..., Encpys q P Fm
q are then sent over the outgoing edges of V . This defines a
network code F for N via FV : px1 , ..., xr q ÞÑ pEncpy1 q, ..., Encpys qq, following the notation above. It
is easy to see that the pair pF, C1 ˆ ¨ ¨ ¨ ˆ CN q achieves the rate k{m ¨ pa1 , ..., aN q in one shot.

8.5

Linear and Non-Linear Network Coding

Theorem 8.2.1 shows that linear network coding suffices to achieve any integer point in the capacity
region of an adversarial network of the form pN , At,0 xEyq, provided that the network alphabet is of
the form Fm
q , with q and m sufficiently large. We now show that this is not the case in general if the
adversary has the form A “ At,0 xU y, where U Ĺ E is a proper subset of vulnerable edges.
Example 8.5.1. Let N be the network in Figure 10. The edges of N are ordered according to their
indices. Let U :“ te1 , e2 , e3 u Ĺ E and A :“ A1,0 xU y.
e1

S

e3

e2

V

e4

T

Figure 10: Network for Example 8.5.1.
It is easy to see that 1 P RpN , Aq for any network alphabet A. We now show that the rate 1
cannot be achieved employing a linear network code at the intermediate vertex V .
Assume that A “ Fm
q for some prime power q and some m ě 1, and that the vertex V processes
the incoming packets according to a linear network code FV : A3 Ñ A (erasures are excluded from
the model). By definition of linear network code (Definition 5.2.1), there exist λ1 , λ2 , λ3 P Fq such
that FV pxq “ λ1 x1 ` λ2 x2 ` λ3 x3 for all x “ px1 , x2 , x3 q P A3 . Moreover, by definition of A we have
ΩF rA; S Ñ inpT qspxq “ tλ1 y1 ` λ2 y2 ` λ3 y3 : y P A3 and yi ‰ xi for at most one value of iu.
Assume by contradiction that there exists a good code C Ď A3 for the channel ΩF rA; S Ñ inpT qs with
|C| “ |A| “ q m ě 2. Then at least one among λ1 , λ2 , λ3 must be non-zero. Without loss of generality,
we may assume λ1 ‰ 0. Let x, x1 P C with x ‰ x1 , and define
y1 :“ λ´1
1 p´λ2 x2 ´ λ3 x3 q, y2 :“ x2 , y3 :“ x3 ,

1
1
1
1
1
1
y11 :“ λ´1
1 p´λ2 x2 ´ λ3 x3 q, y2 :“ x2 , y3 :“ x3 .

Then 0 “ λ1 y1 ` λ2 y2 ` λ3 y3 “ λ1 y11 ` λ2 y21 ` λ3 y31 P ΩF rA; S Ñ inpT qspxq X ΩF rA; S Ñ inpT qspx1 q,
contradicting the fact that C is good for the channel ΩF rA; S Ñ inpT qs.
34

9

Other Adversarial Models

Using the combinatorial framework developed in this work, other adversarial models can be investigated. As already shown for certain of adversaries, Lemma 6.2.1 and 6.2.3 allow to port to the network
context any upper bound for the capacity of channels of the form As 99K Âs . We include the analysis
of error-adversaries having access to overlapping sets of coordinates, and of rank-metric adversaries.
See [35, 36] for a general reference on rank-metric codes in matrix representation.
In the sequel we only consider erasure-free adversarial models, and study the capacities of certain
channels of the form As 99K As , where A is a finite set with |A| ě 2 and s ě 1. All the capacities are
expressed as logarithms in base |A|.
The upper bounds established in this section can be ported to the networking context using the
Porting Lemmas established in Section 6. The details are left to the reader.

9.1

Error-Adversaries Acting on Overlapping Sets of Coordinates

We start by considering L ě 1 adversaries having access to possibly intersecting sets of coordinates
U1 , ..., UL Ď rss. The adversaries have error powers t1 , ..., tL ě 0, and zero erasure powers.
Definition 9.1.1. Let L ě 1 be an integer, and let U1 , ..., UL Ď rss. Let t1 , ..., tL be integers with
tℓ ě 0 for all 1 ď ℓ ď L. Set U :“ pU1 , ..., UL q and t :“ pt1 , ..., tL q. The channel Ht xU y : As 99K As is
defined by
ď
Ht xU y :“
Htpp1q xUpp1q y  ¨ ¨ ¨  HtppLq xUppLq y,
p permutation
of t1,...,su

where Htppiq xUppiq y :“ Htppiq ,0 xUppiq y : As 99K As Ď Âs for all i P rss. See Definition 4.1.3 for details.
Before proceeding with the analysis of channels of type Ht xU y, we observe that the order in which
the adversaries act is in fact irrelevant.
Lemma 9.1.2. Let U1 , U2 Ď rss be sets, and let t1 , t2 ě 0 be integers. Then
Ht1 xU1 y  Ht2 xU2 y “ Ht2 xU2 y  Ht1 xU1 y.
Proof. To simplify the notation, we set H1 :“ Ht1 xU1 y and H2 :“ Ht2 xU2 y. We need to show that
for all x P As we have pH1  H2 qpxq “ pH2  H1 qpxq. By symmetry, it suffices to show that for all
x P As we have pH1  H2 qpxq Ď pH2  H1 qpxq. To see this, fix an arbitrary y P pH1  H2 qpxq. Then by
definition of concatenation there exists z P As such that z P H1 pxq and y P H2 pzq.
Define the sets U 1 :“ t1 ď i ď s : zi ‰ xi u Ď U1 and U 2 :“ t1 ď i ď s : zi ‰ yi u Ď U2 . Now
construct z 1 P As as follows:
$
& yi if i P U 2 ,
for 1 ď i ď s, zi1 :“
x
if i P U 1 zU 2 ,
% i
zi otherwise.

One can directly check that z 1 P H2 pxq and y P H1 pz 1 q. Therefore y P pH2  H1 qpxq. Since y was
arbitrary, this shows that pH1  H2 qpxq Ď pH2  H1 qpxq for all x P As , and concludes the proof.
Proposition 9.1.3. Let L ě 1, U “ pU1 , ..., UL q and t “ pt1 , ..., tL q be as in Definition 9.1.1. Then
Ht xU y “ Ht1 xU1 y  ¨ ¨ ¨  HtL xUL y.
Proof. Apply Lemma 9.1.2 iteratively.
35

The compound zero-error capacity of a channel of type Ht xU y is defined as follows.
Definition 9.1.4. Let L ě 1, U :“ pU1 , ..., UL q and t :“ pt1 , ..., tL q be as in Definition 9.1.1. For
n ě 1, the compound channel Ht xU yn,cp : pAs qn 99K pAs qn is defined by
ď
Ht xU yn,cp :“
Ht xV yn ,
V ĎU
|V |ďt

and the compound zero-error capacity of the channel Ht xU y is the number
C0,cp pHt xU yq :“ sup tC1 pHt xU yn,cp q{n : n P Ně1 u .
We can now state the analogue of Theorem 4.3.1 for the case of error-adversaries acting on possibly
overlapping sets of coordinates.
Theorem 9.1.5. Let L ě 1, U :“ pU1 , ..., UL q and t :“ pt1 , ..., tL q be as in Definition 9.1.1. For all
n ě 1 we have
n ¨ C1 pHt xU yq ď C1 pHt xU yn q ď C1 pHt xU yn,cp q ď n ps ´ σt xU yq ,
where
ˇ
+
#ˇ
L
ˇ
ˇď
ˇ
ˇ
ˇ pjq ˇ
ˇ
pjq
p1q
p2q ˇ
σt xU y :“ max ˇ Uℓ Y Uℓ ˇ : Uℓ Ď Uℓ and ˇUℓ ˇ ď tℓ for all 1 ď ℓ ď L and j “ 1, 2
ˇ
ˇ
ℓ“1

is a parameter which we call the adversarial strength. In particular,

C1 pHt xU yq ď C0 pHt xU yq ď C0,cp pHt xU yq ď s ´ σt xU y.
Moreover, all the above inequalities are achieved with equality if A “ Fq and q is sufficiently large.
To prove Theorem 9.1.5, we will need the following preliminary lemma.
Lemma 9.1. Let L ě 1, U :“ pU1 , ..., UL q and t :“ pt1 , ..., tL q be as in Definition 9.1.1. Fix any sets
1
2
U ℓ , U ℓ , Ď Uℓ , for 1 ď ℓ ď L, that achieve the maximum in the definition of the adversarial strength
σt xU y (see Theorem 9.1.5). Let
L
ď
1
2
U :“
Uℓ Y Uℓ,
ℓ“1

and define V :“
Ht xV ypxq X Ht xV

1
1
pU 1 , ..., U L q Ď U , V 1
1 ypx1 q ‰ H whenever x
i

2

2

“ pU 1 , ..., U L q Ď U . Then for any x, x1 P As we have
“ x1i for all i P rsszU .
1

2

Proof. To simplify the notation, let Vℓ :“ U ℓ and Vℓ1 :“ U ℓ for all ℓ P t1, ..., Lu. Let x, x1 P As with
xi “ x1i for all i P rsszU . We will explicitly construct a vector z P Ht xV ypxq X Ht xV 1 ypx1 q. First of all,
define the sets
L
L
ď
ď
1
1
V :“
Vℓ , V :“
Vℓ1 , W :“ V Y V .
ℓ“1

ℓ“1

Note that, by construction, W Ě U . Therefore xi “ x1i for all i P rsszW . To construct z, recursively
define vectors zr0s, ..., zrLs P As and z 1 r0s, ..., z 1 rLs P As as follows. Set zr0s :“ x and z 1 r0s :“ x1 .
Then for all 1 ď ℓ ď L define
"
" 1
xi
if i P Vℓ1 zV ,
xi
if i P Vℓ ,
1
for 1 ď i ď s.
z rℓsi :“
zrℓsi :“
1
zrℓ ´ 1si otherwise,
z rℓ ´ 1si otherwise,
36

By construction, for all 1 ď ℓ ď L we have
zrℓs P Htℓ xVℓ ypzrℓ ´ 1sq

z 1 rℓs P Htℓ xVℓ1 ypz 1 rℓ ´ 1sq.

and

By definition of Ht xV y and Ht xV 1 y we have zrLs P Ht xV ypxq and z 1 rLs P Ht xV 1 ypx1 q. However, it is
easy to see that zrLs “ z 1 rLs. Therefore we can take z :“ zrLs “ z 1 rLs.
Proof of Theorem 9.1.5. The fact that n ¨ C1 pHt xU yq ď C1 pHt xU yn q ď C1 pHt xU yn,cp q can be easily
shown. We only establish the theorem for σ :“ σu xU y ă s. The case σ “ s is similar. It suffices to
show that C1 pHt xU yn,cp q ď nps ´ σq for all n ě 1, and that for A “ Fq and sufficiently large q we
have C1 pHt xU yq ě s ´ σ.
1
2
We let U ℓ , U ℓ (for 1 ď ℓ ď L) and U be as in Lemma 9.1. Note that, in particular, σ “ |U |. In
the sequel we denote by π : As Ñ As´σ the projection on the coordinates outside U .
Let n ě 1 be an integer. Then π extends component-wise to a map Π : pAs qn Ñ pAs´σ qn . Let
C Ď pAs qn be a capacity-achieving good code for Ht xU yn,cp . To obtain the upper bound, it suffices to
show that the restriction of Π to C is injective.
Take x, x1 P C, and assume Πpxq “ Πpx1 q. We will show that x “ x1 . Write x “ px1 , ..., xn q and
1
x “ px11 , ..., x1n q. By definition of Π, we have πpxk q “ πpx1k q for all 1 ď k ď n. By Lemma 9.1, the
1
1
2
2
L-tuples V :“ pU 1 , ..., U L q Ď U and V 1 :“ pU 1 , ..., U L q Ď U satisfy:
|V |, |V 1 | ď t

and

Ht xV ypxk q X Ht xV 1 ypx1k q ‰ H

for all 1 ď k ď n.

(27)

By definition of Ht xU yn,cp we have

Ht xU yn,cp pxq X Ht xU yn,cp px1 q Ě Ht xV yn px1 , ..., xn q X Ht xV 1 yn px11 , ..., x1n q
n ´
¯
ź
Ht xV ypxk q X Ht xV 1 ypx1k q ‰ H,
“
k“1

where the last inequality follows from (27). Since C is good for Ht xU yn,cp , we conclude x “ x1 . This
shows that the restriction of Π to C is injective, as desired.
We now prove that the upper bounds in the theorem are tight for A “ Fq and q sufficiently large.
As already stated, it suffices to show that C1 pHt xU yq ě s ´ σ. Let C Ď Fsq be code with cardinality
q s´σ and minimum distance dH pCq “ σ ` 1. We will show that C is good for Ht xU y. Let x, x1 P C
be arbitrary with x ‰ x1 . Assume by contradiction that there exists z P Ht xU ypxq X Ht xU ypx1 q.
Then by definition of Ht xU y and Proposition 9.1.3 there exist vectors zr0s, zr1s, ..., zrLs P As and
z 1 r0s, z 1 r1s, ..., z 1 rLs P As with the following properties: zr0s “ x, z 1 r0s “ x1 , zrLs “ z 1 rLs “ z,
zrℓs P Htℓ xUℓ ypzrℓ ´ 1sq and z 1 rℓs P Htℓ xUℓ ypz 1 rℓ ´ 1sq

Now for 1 ď ℓ ď L define the sets

Uℓ1 :“ t1 ď i ď s : zrℓsi ‰ zrℓ ´ 1si u

for all 1 ď ℓ ď L.

Uℓ2 :“ t1 ď i ď s : z 1 rℓsi ‰ z 1 rℓ ´ 1si u.

and

By the construction of the Uℓj ’s and the definition of σu xU y, we have
ˇ
ˇ
L
ˇď
ˇ
ˇ
ˇ
σ “ σu xU y ě ˇ Uℓ1 Y Uℓ2 ˇ .
ˇ
ˇ
ℓ“1

On the other hand,

t1 ď i ď s : zi ‰ xi or zi ‰ x1i u Ď

˜

L
ď

ℓ“1

Uℓ1

¸

Y

˜

L
ď

ℓ“1

Uℓ2

¸

“

L
ď

ℓ“1

Uℓ1 Y Uℓ2 .

Therefore the vectors z, x and x1 must agree in at least s ´ σ components. In particular, we have
dH px, x1 q ď σ, a contradiction.
37

Theorem 9.1.5 can be ported to the network context to study the scenario where multiple adversaries have access to possibly overlapping sets of network edges, and can corrupt up to a certain
number of them.

9.2

Rank-Metric Adversaries

In this section we let A :“ Fm
q , and study adversarial channels whose input and output alphabet
, where m and s are positive integers. In the sequel, we denote by
is the matrix space As – Fmˆs
q
M1 , ..., Ms the columns of a matrix M P Fmˆs
. We consider an adversary who can access only some
q
of the columns of a matrix M P Fmˆs
,
and
is
able to change M in any matrix N P Fmˆs
such that
q
q
rkpN ´ M q ď t, where t ě 0 is an integer measuring the adversary’s power.
Definition 9.2.1. Let m, s ě 1 and t ě 0 be integers, and let U Ď rss be a subset. The matrix
channel Rt xU y : Fmˆs
99K Fmˆs
is defined, for all M P Fmˆs
, by
q
q
q
Rt xU ypM q :“ tN P Fmˆs
: rkpN ´ M q ď t and Mi “ Ni for all i R U u.
q

The one-shot capacity and zero-error capacity of a rank-metric channel Rt xU yq are as follows.
Theorem 9.2.2. Let m, s ě 1 and t ě 0 be integers, and let U Ď rss. For all n ě 1 we have
n ¨ C1 pRt xU yq ď C1 pRt xU yn q ď n ps ´ mint2t, |U |uq .

In particular,
C1 pRt xU yq ď C0 pRt xU yq ď s ´ mint2t, |U |u.

Moreover, all the above inequalities are achieved with equality, provided that q ě m ě s.
Proof of Theorem 9.2.2. Define σ :“ mint2t, |U |u. By Proposition 2.4.4, it suffices to show that
C1 pRt xU yn q ď n ps ´ σq for all n ě 1, and that for q ě m ě s we have C1 pRt xU yq ě s ´ σ. We only
1
2
1
2
prove the theorem for σ ă s. The case σ “ s is similar. Fix sets U , U Ď U with |U |, |U | ď t and
1
2
1
2
|U Y U | “ mint2t, |U |u “ σ. Let U :“ U Y U .
mˆps´σq
Ñ Fq
the projection on the columns indexed by rsszU , and extend π
Denote by π : Fmˆs
q
component-wise to a projection map
Π : Fmˆns
Ñ Fmˆnps´σq
.
q
q
Reasoning as in the proof of Theorem 9.1.5, one can show that the restriction of Π to any good code
for Rt xU yn is injective. This shows the desired upper bound on C1 pRt xU yn q.
C Ď Fmˆns
q
Now assume q ě m ě s. If 2t ě |U |, then we trivially have C1 pRt xU yq ě s ´ σ. If 2t ă |U |, then
be a rank-metric code in matrix representation [35, 36] of minimum rank distance 2t ` 1
let C Ď Fmˆs
q
and cardinality |C| “ q mps´2tq “ q mps´σq . It is easy to see that C is good for Rt xU y.
Theorem 9.2.2 can now be ported to the network context to study the scenario where an adversary
has access to the packets on a given subset U Ď E of edges, and can corrupt them by reducing by at
most t the rank of the m ˆ |U | matrix whose columns are the packets.

10

Conclusions

In this paper, we have proposed a combinatorial framework for adversarial network coding. We
have derived upper bounds for three notions of capacity region (by porting results for Hamming-type
channels to the networking context in a systematic way) and have given some capacity-achieving
coding schemes.
The results of this paper determine (for sufficiently large network alphabets) the three capacity
regions of the following multi-source network adversarial models:
38

• error-free networks,
• a single error-adversary with access to all the network edges,
• a single adversary who can corrupt/erase a fraction of the components of any alphabet symbol.
In the three models above, any integer point in the capacity regions can be achieved using linear
network coding, possibly combined with link-level encoding/decoding. Moreover, in compound adversarial models the use of a large network alphabet (whose size grows in general exponentially with the
number of sources) can be avoided by using the network multiple times.
Even small modifications of these models (such as restricting the adversary to a subset of edges)
give rise to capacity regions whose integer points cannot be achieved in general with linear network
coding.
In this paper, we have derived cut-set upper bounds for the three capacity regions associated with
multiple (possibly coordinated) adversaries, who can only operate on prescribed subsets of the network
edges. The problem of determining the various capacity regions in this generalized adversarial models
remains open.

References
[1] N. Cai and R. W. Yeung, “Network error correction, II: Lower bounds,” Commun. Inf. Sys.,
vol. 6, no. 1, pp. 37–54, 2006.
[2] R. W. Yeung and N. Cai, “Network error correction, I: Basic concepts and upper bounds,”
Commun. Inf. Sys., vol. 6, no. 1, pp. 19–35, 2006.
[3] S. Yang and R. W. Yeung, “Refined coding bounds for network error correction,” in Proc. IEEE
Info. Theory Workshop on Info. Theory for Wireless Netw., Solstrand, Norway, Jul. 2007, pp.
1–5.
[4] S. Yang, C. K. Ngai, and R. W. Yeung, “Construction of linear network codes that achieve a
refined Singleton bound,” in Proc. IEEE Int. Symp. on Info. Theory, vol. 7, Nice, France, Jun.
2007.
[5] S. Yang and R. W. Yeung, “Characterizations of network error correction/detection and erasure
correction,” in Proc. 3rd Workshop on Network Coding, Theory, and Appl., San Diego, CA, Jan.
2007.
[6] Z. Zhang, “Linear network error correction codes in packet networks,” IEEE Trans. Info. Theory,
vol. 54, no. 1, pp. 209–218, Jan. 2008.
[7] S. Yang, R. W. Yeung, and Z. Zhang, “Weight properties of network codes,” Trans. Emerg.
Telecommun. Techn., vol. 19, no. 4, pp. 371–383, Jun. 2008.
[8] R. Matsumoto, “Construction algorithm for network error-correcting codes attaining the Singleton bound,” IEICE Trans. Fund. Electr. Commun. & Comp. Sci., vol. E90-A, no. 9, pp.
1729–1735, Sep. 2007.
[9] S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Médard, and M. Effros, “Resilient network
coding in the presence of Byzantine adversaries,” IEEE Trans. Info. Theory, vol. 54, no. 6, pp.
2596–2603, Jun. 2008.
[10] L. Nutman and M. Langberg, “Adversarial models and resilient schemes for network coding,” in
Proc. IEEE Int. Symp. Info. Theory, Toronto, Canada, Jul. 2008, pp. 171–175.
39

[11] O. Kosut, L. Tong, and D. N. C. Tse, “Polytope codes against adversaries in networks,” IEEE
Trans. Info. Theory, vol. 60, no. 6, pp. 3308–3344, Jun. 2014.
[12] D. Wang, D. Silva, and F. R. Kschischang, “Constricting the adversary: A broadcast transformation for network coding,” in Proc. 45th Annual Allerton Conference on Commun., Control and
Computing, Allerton House, Monticello, IL, Sep. 2007.
[13] R. Kötter and F. R. Kschischang, “Coding for errors and erasures in random network coding,”
IEEE Trans. Info. Theory, vol. 54, no. 8, pp. 3579–3591, Aug. 2008.
[14] D. Silva, F. R. Kschischang, and R. Kötter, “A rank-metric approach to error control in random
network coding,” IEEE Trans. Info. Theory, vol. 54, no. 9, pp. 3951–3967, Sep. 2008.
[15] D. Silva and F. R. Kschischang, “On metrics for error correction in network coding,” IEEE Trans.
Info. Theory, vol. 55, no. 12, pp. 5479–5490, Dec. 2009.
[16] S. Jaggi, M. Langberg, T. Ho, and M. Effros, “Correction of adversarial errors in networks,” in
Proc. IEEE Int. Symp. on Info. Theory, Adelaide, Australia, Sep. 2005, pp. 1455–1459.
[17] T. Ho, B. Leong, R. Kötter, M. Médard, M. Effros, and D. R. Karger, “Byzantine modification
detection in multicast networks with random network coding,” IEEE Trans. Info. Theory, vol. 54,
pp. 2798–2803, Jun. 2008.
[18] S. Vyetrenko, T. Ho, and E. Erez, “On noncoherent correction of network errors and erasures
with random locations,” in Proc. IEEE Int. Symp. on Info. Theory, Seoul, Korea, Jun. 2009, pp.
996–1000.
[19] O. Kosut and J. Kliewer, “Equivalence for networks with adversarial state,” IEEE Transactions
on Information Theory, 2017, to appear, DOI: 10.1109/TIT.2017.2701804.
[20] M. Jafari Siavoshani, C. Fragouli, and S. Diggavi, “Noncoherent multisource network coding,” in
Proc. IEEE Int. Symp. on Info. Theory, Toronto, Canada, Jul. 2008, pp. 817–821.
[21] S. Mohajer, M. Jafari Siavoshani, S. N. Diggavi, and C. Fragouli, “On the capacity of multisource
non-coherent network coding,” in Proc. IEEE Info. Theory Workshop on Netw. and Info. Theory,
Volos, Greece, Jun. 2009, pp. 130–134.
[22] M. Jafari Siavoshani, C. Fragouli, and S. Diggavi, “Code construction for multiple sources network
coding,” in Proc. 10th ACM Int. Symp. Mobile Ad Hoc Netw. and Comp., New Orleans, LA, May
2009, pp. 21–24.
[23] 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 Trans. Info. Theory,
vol. 57, no. 2, pp. 1067–1079, Feb. 2011.
[24] C. E. Shannon, “The zero error capacity of a noisy channel,” IRE Trans. Info. Theory, vol. 2,
no. 3, pp. 8–19, 1956.
[25] R. Kötter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Trans. Netw.,
vol. 11, no. 5, pp. 782–795, Oct. 2003.
[26] J. Körner and A. Orlitsky, “Zero-error information theory,” IEEE Trans. Info. Theory, vol. 44,
pp. 2207–2229, Jun. 1998.

40

[27] M. Fekete, “Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten,” Mathematische Zeitschrift, vol. 17, no. 1, pp. 228–249, 1923.
[28] J. M. Steele, Probability Theory and Combinatorial Optimization. Society for Indust. and Appl.
Math., 1997.
[29] L. Lovász, “On the Shannon capacity of a graph,” IEEE Trans. Info. Theory, vol. 25, no. 1, pp.
1–7, Jan. 1979.
[30] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed.
The MIT Press, 2009.
[31] K. Menger, “Zur allgemeinen Kurventheorie,” Fundamenta Mathematicae, vol. 10, no. 1, pp.
96–115, 1927.
[32] W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes.
Press, 2010.

Cambridge University

[33] F. R. Kschischang, “An introduction to network coding,” in Network Coding, Fundamentals and
Applications, M. Médard and A. Sprintson, Eds. Elsevier, 2012.
[34] E. M. Gabidulin, “Theory of codes with maximum rank distance,” Probl. Peredachi Informatsii,
vol. 21, no. 1, pp. 3–16, 1985.
[35] P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory,” J. Comb. Th.
A, vol. 25, no. 3, pp. 226–241, 1978.
[36] A. Ravagnani, “Rank-metric codes and their duality theory,” Designs, Codes, and Crypt., vol. 80,
no. 1, pp. 197–216, Jul. 2016.

A

Proofs

Proof of Proposition 3.1.6. For 1 ď k ď n and 1 ď i ď m, we denote by Xk,i and Yk,i the input and
output alphabets, respectively, of channel Ωk,i . By assumption, we have Yk,i Ď Xk,i`1 for all 1 ď k ď n
and for all 1 ď i ď m ´ 1. We need to prove that for all px1,1 , ..., xn,1 q P X1,1 ˆ ¨ ¨ ¨ ˆ Xn,1 one has
˜
¸
˜˜
¸
˜
¸¸
n
n
n
ź
ź
ź
pΩk,1  ¨ ¨ ¨  Ωk,m q px1,1 , ..., xn,1 q “
Ωk,1  ¨ ¨ ¨ 
Ωk,m
px1,1 , ..., xn,1 q.
k“1

k“1

k“1

We will only show the inclusion Ď. The other containment can be seen similarly. Fix an arbitrary
˜
¸
n
ź
py1,m , ..., yn,m q P
pΩi,1  ¨ ¨ ¨  Ωi,mq px1,1 , ..., xn,1 q Ď Y1,m ˆ ¨ ¨ ¨ ˆ Yn,m .
k“1

By definition of product, for all 1 ď k ď n we have yk,m P pΩk,1  ¨ ¨ ¨  Ωk,mqpxk,1 q. Thus, by
definition of concatenation, for any integer 1 ď k ď n there exist elements xk,2 , ..., xk,m with the
following properties:
xk,i P Ωk,i´1 pxk,i´1 q Ď Yk,i´1 Ď Xk,i for all 2 ď i ď m,

and

yk,m P Ωk,m pxk,m q.

Therefore we have px1,i , ..., xn,i q P pΩ1,i´1 ˆ ¨ ¨ ¨ ˆ Ωn,i´1 qpx1,i´1 , ..., xn,i´1 q for all 2 ď i ď m, and
py1,m , ..., yn,m q P pΩ1,m ˆ Ωn,m qpx1,m , ..., xn,m q. This implies
˜˜
¸
˜
¸¸
n
n
ź
ź
py1,m , ..., yn,m q P
Ωk,1  ¨ ¨ ¨ 
Ωk,m
px1,1 , ..., xn,1 q.
k“1

k“1

41

Proof of Proposition 3.2.2. Denote by Xj and Yj the input (resp., output) alphabets of channel Ωj ,
for j P t1, 2u. By definition of adversarial channel, we need to show that for all x1 P X1 we have
¸
¸
˜
¸
˜
˜
ď
ď
pΩ1  Ωi  Ω2 q px1 q “ Ω1 
Ωi  Ω2 px1 q.
iPI

iPI

Ť
Let us show the inclusion Ď. Take an arbitrary y2 P p iPI pΩ1  Ωi  Ω2 qq px1 q. Then there exist
ι P I, y1 P ŤY1 Ď X and y P Y such that: y1 P Ω1 px1 q, y P Ωι py1 q, and y2 P Ω2 pyq. Therefore
y2 P pΩ1  p iPI Ωi q  Ω2 q px1 q, as desired. The other inclusion can be shown similarly.
Proof of Lemma 4.3.2. Part 1 is straightforward, and part 2 follows from the fact that the Uℓ ’s are
pairwise disjoint. Let us show part 3. For all 1 ď ℓ ď L define the sets Vℓ , Vℓ1 Ď Uℓ by
1

‹

‹

2

Vℓ1 :“ U ℓ Y U ℓ .

Vℓ :“ U ℓ Y U ℓ ,

We claim that V :“ pV1 , ..., VL q and V 1 :“ pV11 , ..., VL1 q have the desired properties. First of all,
|V |, |V 1 | ď t ` e by construction. Now let x, x1 P As , and assume xi “ x1i for all i P rsszU . We will
explicitly construct a vector z P Ht,e xV ypxq X Ht,e xV 1 ypx1 q. Define the auxiliary sets
‹

U :“

L
ď

‹

Uℓ,

V :“

ℓ“1

L
ď

ℓ“1

Vℓ ,

1

V :“

L
ď

Vℓ1 .

ℓ“1
‹

1

‹

The previous unions are disjoint unions. Moreover, by construction, we have V Ě U and V Ě U .
Define z P As as follows:
$
‹
‹
if i P U ,
’
’
‹
&
x1i
if i P V zU ,
for 1 ď i ď s, zi :“
1
’
xi
if i P V zV ,
’
%
xi “ x1i otherwise.
1

1

Note that the vector z is well defined. Indeed, we have xi “ x1i for all i R V Y V , as V Y V Ě U . One
can directly check that z P Ht,e xV ypxq X Ht,e xV 1 ypx1 q.

42

