Title: Adversarial Network Coding

Abstract: In the context of Network Coding, one or more sources of information attempt to transmit messages to multiple receivers through a network of intermediate nodes. In order to maximize the throughput, the nodes are allowed to recombine the received packets before forwarding them towards the sinks.

In this talk, we present a mathematical model for adversarial network transmissions, studying the scenario where one or multiple (possibly coordinated) adversaries can maliciously corrupt some of the transmitted messages, according to certain restrictions. For example, the adversaries may be constrained to operate on a vulnerable region of the network. 

If noisy channels (traditionally studied in Information Theory) are described within a theory of "probability", adversarial channels are described within a theory of "possibility". Accordingly, in this talk we take a discrete combinatorial approach in defining and studying network adversaries and channels.

We propose various notions of capacity region of an adversarial network, and illustrate a general technique that allows to port upper bounds for the capacities of point-to-point channels to the networking context. We then present some new upper bounds on the capacity regions of an adversarial network, and describe some new capacity-achieving communication schemes.

The new results in this talk are joint work with Frank R. Kschischang (University of Toronto).