Graph Guessing Games and new laws of Information Theory – University of Copenhagen

Graph Guessing Games and new laws of Information Theory

Talk by Søren Riis

Abstract:

We will consider some graph guessing games that, at first, may
just look like recreational mathematics. However, graph guessing
games have some interesting relationships to communication
networks (network coding), coding theory (index coding) and
multiuser information theory.

I will give an example of a concrete 10 node graph where
Shannon's classic laws of information theory only give
sub-optimal bounds on the optimal result for the Graph Guessing
Game. Better bounds can be derived using recently discovered
Non-Shannon information inequalities.  The main theorems can be
derived using linear algebra, but since the calculations are very
long, all major derivations were done by computer.  This raises
some general issues concerning machine generated proofs. The
proofs are in principle 100% readable by humans, but the computer
generated derivations were well in access of 10000 pages.

The above graph was found in collaboration with some of my PhD
students and postdoctoral students using an extensive computer
search.

The talk is aimed at a non-specialist audience who might want to
work on some of the open questions in the area.

 

Søren Riis,
Queen Mary,
University of London