Speaker: |
Venkat Anantharam (University of California at Berkeley Department of Electrical Engineering and Computer Science 271 Cory Hall Berkeley, California 94720-1770 United States of America) |

Organiser: |
Sandeep K Juneja |

Date: |
Thursday, 30 Mar 2017, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Consider a graph whose vertices and edges carry marks, viewed as data samples associated to the vertex or the edge respectively. For example the vertices might be individuals, the vertex mark might describe the musical taste of the individual and the edge mark might describe the degree of anity between the corresponding pair of individuals. We pose the problem of representing the information content of such a marked graph in the most ecient way possible. Further, we would like to do this in a universal sense, i.e., in eect, without making any statistical assumptions about the data sample being compressed. It turns out that one can make precise sense of this question in the language of the local weak limit theory, the only assumption being that the graph is sparse, i.e. that the number of edges is on the same scale as the number of vertices. What is more, the compression can be done in the most ecient way possible. Namely one can make sense of a notion of entropy associated to the local weak limit, which is on a linear scale in the number of nodes, and one can compress down to this entropy in a universal sense. The entropy notion we work with is a generalized version of the one introduced by Bordenave and Caputo (2014).

All the necessary background from the theory of local weak limits that is needed will be developed during the talk (joint work with Payam Delgosha).