Wojciech Szpankowski (Purdue University)
Abstract. F. Brooks argued in his 2003 JACM paper on the challenges of computer sciences that there is "no theory that gives us a metric for the information embodied in structure." C. Shannon himself noticed this fifty years earlier in his 1953 paper. More generally, we lack an information theory of data structures (e.g., graphs, sets, social networks, chemical structures, biological networks). In this talk, we present some recent research results on structural information. We first propose some fundamental limits of information content for a wide range of data structures with correlated labels and then propose asymptotically optimal lossless compression algorithms achieving these limits for unlabeled graphs. Then we move to Markov fields and try to understand structural properties of large systems with local mutual dependencies and interaction. "sfi14" 51 lines, 2727 characters fields and try to understand structural properties of large systems with local mutual dependencies and interaction. In particular, we focus on enumerating Markov field types. We tackle most of these problems by complex analysis methods, thus within the realm of analytic information theory.