Seminar: Graphs and Algebra in Modern Communication

The origin of communication is based on the concept of two users exchanging information with each other over a single channel. The problem of perfect communication over a channel was modeled by Shannon in the late 40s. More modern communication networks are not so restrictive though. Most of the networks we use nowadays, connect multiple parties and graphs can be exploited to represent these networks. The question we are going to investigate in this seminar is simple: given a graph representing a network, what is its capacity, meaning how much information can be sent through it, and by which communication protocol? This question has been already answered for unicast networks, meaning networks between a single source and a single receiver, and for multicast networks, meaning networks used by a source to communicate simultaneously to multiple receivers.

The capacity of communication for most networks with multiple sources is still an open question. Networks of this type are characterized by interference that is represented by the messages sent by undesired sources. A communication strategy has to be determined in order to remove the interference. We will focus our work on multiple unicast networks and look at the effectiveness of a practice known as interference alignment. We will define the concepts of linear capacity region of a network and discover that the points of this region are in relation with the solutions of a system of bilinear of equation. Solving such a system is know to be hard in general, so we will finally find the points of this region that are achievable by mean Gaussian elimination.