Workshop abstracts

The talks are in room 103, Mathematical Sciences; tea/coffee in room 102.

Tuesday 11 September: Tutorials

    • 10:00-11:00: Max Gadouleau, Network Coding
    • 11:00-11:30: Refreshments
    • 11:30-12:30: Søren Riis, Graph Entropy, Guessing Games and the Term Model

I present a mathematical framework for discussing communication networks. The talk introduces a very clean and simple mathematical model. This model can be studied for its own sake as well as be applied to describe and analyse a number of phenomena (e.g. link failures, change network topology) in communication networks. In the talk I raise a number of fundamental questions. The framework I introduce facilitates tackling a number of long standing open questions in Complexity Theory and in Information Theory.  I illustrate this by showing how I used the framework to settle 3 conjectures by Leslie Valiant (from the mid 90s).  The talk is self contained and aimed mainly at (pure) Mathematicians and Computer Scientists who value beauty. 

    • 12:30-14:00: Lunch
    • 14:00-15:00: Terence Chan, Mission Impossible: Characterising Network Coding Regions

      The prevailing approach for data transport in communications networks is routing. Packets travel from source to destination via intermediate routers, which switch packets from incoming links onto outgoing links. This approach is ubiquitous in packet switched networks such as the Internet. The underlying conceptual model is physical commodity flow, e.g. highway traffic or water in pipes. If multiple packets wish to simultaneously occupy the same link, some packets must wait or be dropped. Network coding stems from the realisation that information is fundamentally different to physical commodities. Intermediate nodes can perform more general data processing, rather than just switching. For example, packets can be combined via modulo 2 addition. Network coding is practically and theoretically significant. Not only can it increase throughput, it is robust to link failures, and can minimise delay or transmission cost. This tutorial will begin with an introduction of network coding and its applications in distributed data storage network.Characterising the network coding region (i.e., the set of achievable source transmission rate and link capacity tuples) is a fundamental question in network coding. The problem is completely solved for single source multicast (one source with several receivers): The network coding region is characterised by max-flow/min-cut bound. Optimal network codes can also be found easily in this case. In contrast, finding optimal routes and maximum routing throughput is fundamentally hard. In the general non-multicast setting, the problem is still an open challenge.The second part of the tutorial will focus on existing results in addressing this challenging problem. Specifically, we will cover the following topics:

      • Characterisation of network coding region by entropy functions
      • Dualities between characterisation of network coding regions and information inequalities
      • Linear Programming (LP) bounds
      • Constrained network coding

      LP bound is probably the most tightest computable bound in existing literature. However, one of its deficiency is its high computational complexity: Both the number of variables and the number of constraints increase exponentially with the number of links in the network, making the bound computationally infeasible even for modest networks. The third part of the tutorial will examine several computationally efficient “network-based” bounds, including the cut-set bounds, the functional dependency bounds and the network sharing bounds.

    • 15:00-15:30: Fabrizio Smeraldi, The Thermodynamics of Confidentiality 

Interest in the thermodynamics of computation dates back to the pioneers of computing. A major achievement is the proof that computing can in principle be done reversibly at no energy cost. However, an important type of computation – secure computation –
is intrinsically irreversible. In this talk I’ll outline the fundamental relation
between dissipativity and security and show that one of the main metrics of
confidentiality used in the security community, namely information leakage, essentially
measures dissipation in the thermodynamic sense.  With confidentiality now grounded in Thermodynamics, Landauer’s principle implies a fundamental lower bound to the
energetic cost of secure computation.  This is joint work with Dr Pasquale Malacaria
at Queen Mary University of London. 

    • 15:30-16:00: Refreshments
    • 16:00-16:30: Peter Cameron, Combinatorial Representations

      Motivated by a question about the effect of alphabet size in network coding problems, we (Max Gadouleau, Søren Riis and I) defined the notion of combinatorial representation of a family of r-subsets of a set, generalising the (dual) notion of vector representation of a matroid. Indeed, a family with a combinatorial representation by linear functions in a vector space over a finite field is a (representable) matroid. It turns out that every family of sets has a combinatorial representation over some alphabet, while for r=2, every family (that is, every graph) has representations over all sufficiently large alphabets. (The proof of this generalises the existence of sets of mutually orthogonal Latin squares, and uses Richard Wilson’s existence theory for pairwise balanced designs.) Various matroid-theoretic and information-theoretic concepts such as rank and entropy can be extended to combinatorial representations.


    • 16:30-17:00: Bill Jackson, Nowhere-zero Flows in Graphs

Nowhere-zero flows were introduced by W T Tutte in 1950 as a dual concept to proper vertex colourings. He showed that a connected plane graph has a proper k-vertex-colouring if and only if its planar dual has a nowhere-zero k-flow. The two concepts are completely different for non-planar graphs, however. I will introduce the concept of a nowhere-zero k-flow and the related flow polynomial of a graph, describe long standing open problems of Tutte, Jaeger and Welsh, and report on the progress which has been made on these problems. 

Wednesday 12 September: Talks

  • 9:30-10:30: Terence Chan, Aspects of Information Inequalities and their Applications

    Information inequalities are well-known as the basic laws governing the fundamental limits in data transmission and compression. They are critical tools in proving converse coding theorems in communications. These inequalities are also closely related to other areas including matroid theory, group theory, linear algebra, algorithmic complexity, determinantal inequalities and many others. In this talk, we will cover various interesting aspects of information inequalities and entropic polymatroids. Relations between inequalities for groups and information inequalities will be derived and properties for entropic polymatroids induced by groups and vector spaces will be discussed. As an application, we will also demonstrate how information inequalities can be used to characterise throughput in networks.

  • 10:30-11:00: Refreshments
  • 11:00-11:30: Raul Mondragon, Maximum Entropy and the Rich Club in Networks

In a network,  the density of links between nodes of high degree (rich nodes) is measured by the rich–club coefficient.  The rich-club coefficient is  associated with the dispersion of information via the number of alternative routes and the length of the shortest paths. In this talk, using  a maximal  entropy approach,  we describe recent results about the “maximally noncommittal  knowledge” of 

the network structure when the rich-club coefficient and the degree sequence are conserved.

  • 11:30-12:00: Anh Dang, Rahil Baber and Søren Riis,  Examples and Counter Examples in network coding – a special graph on 10 nodes
  • 12:00-13:30: Lunch
  • 13:30-14:30: Max Gadouleau, Closure Solvability
  • 14:30-15:00: Rui Carvalho, Fair sharing of resources in supply networks

We investigate the fair allocation of network resources an all-important issue for the efficiency of transportation networks all around us. We analyse a generic mechanism that distributes network capacity fairly among existing flow demands. When the number of intersections is the maximum and the distance between the source and the sink is large, we find that a fair allocation implies a decrease of at least 50% from the maximum throughput. We also find that the flow allocations assigned to the agents decays as a power-law with exponent -1. Our semi-analytical framework suggests possible explanations for the well-known reduction of the throughput in fair allocations. This raise the following general problem that the combination of network topology and routing rules can lead to highly uneven (but fair) distributions of resources.  A remark of caution to network designers but maybe an interesting challenge for mathematicians.

  • 15:00-15:30: Refreshments
  • 15:30-16:00: Peter Cameron, Synchronization
  • 16:00-16:30: Søren Riis, Some Unsolvable and Some Unsolved Problems in Network Coding

I present a new type of result in Universal Algebra that involves the Term Model, Graph Entropy and Guessing Games introduced in the tutorials. I then explain how the result can be applied to investigate routing strategies in dynamic communication networks.  Finally I present a (wrong looking) theorem related to the min-cut max-flow theorem for the Term Model:

  1. It is undecidable to determine if a given network can achieve a max-flow greater or equal to a given integer
  2. There is a polynomial time algorithm which determines if a given network can achieve a max-flow greater to a given integer.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s