Hi all,

some or all of you might be interested in the talk below.

Best,

-joe

From: Michael Tschannen michaelt@nari.ee.ethz.ch Subject: Talk: "Structural Information" by Prof. Wojciech Szpankowski, Purdue University, on Tuesday, September 27th 2016, 4.15 pm, HG D 3.2 Date: 20 September 2016 at 10:14:57 GMT+2 To: wiss-mitarb@ee.ethz.ch

Dear colleagues,

you are cordially invited to attend the following talk by Professor Wojciech Szpankowski, Purdue University:

Title: "Structural Information"

Time and place: Tuesday, September 27th 2016, 4.15 pm in HG D 3.2

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 and binary (plane and non-plane) trees. Then we shall discuss a different structural information by considering a channel that maps binary sequences to self-avoiding walks in the two-dimensional grid, inspired by a model of protein statistics. This channel, which we also call the Boltzmann sequence-structure channel, is characterized by a Boltzmann/Gibbs distribution with a free parameter corresponding to temperature. The capacity of this channel appears to exhibit a phase transition for small temperature and decays to zero for high temperature. If time allows we also discuss structural properties of large systems with local mutual dependencies and interaction, focusing on enumerating Markov fields and universal types. We tackle most of these problems by complex analysis methods, thus within the realm of analytic information theory.

Bio: Wojciech Szpankowski is Saul Rosen Distinguished Professor of Computer Science at Purdue University where he teaches and conducts research in analysis of algorithms, information theory, bioinformatics, analytic combinatorics, random structures, and stability problems of distributed systems. He received his M.S. and Ph.D. degrees in Electrical and Computer Engineering from Gdansk University of Technology. He held several Visiting Professor/Scholar positions, including McGill University, INRIA, France, Stanford, Hewlett-Packard Labs, Universite de Versailles, University of Canterbury, New Zealand, Ecole Polytechnique, France, the Newton Institute, Cambridge, UK, ETH, Zurich, Gdansk University of Technology, and Jagiellonian University, Poland. He is a Fellow of IEEE, and the Erskine Fellow. In 2010 he received the Humboldt Research Award and in 2015 the inaugural Arden L. Bement Jr. Award. He published two books: "Average Case Analysis of Algorithms on Sequences", John Wiley & Sons, 2001, and "Analytic Pattern Matching:

From DNA to Twitter", Cambridge, 2015. He has been a guest editor and

an editor of technical journals, including Theoretical Computer Science, the ACM Transaction on Algorithms, the IEEE Transactions on Information Theory, Foundation and Trends in Communications and Information Theory, Combinatorics, Probability, and Computing, and Algorithmica. In 2008 he launched the interdisciplinary Institute for Science of Information, and in 2010 he became the Director of the newly established NSF Science and Technology Center for Science of Information.

We very much look forward to seeing you there.

Best wishes,

Michael Tschannen

-- Michael Tschannen ETH Zurich, Communication Technology Laboratory Sternwartstrasse 7 CH-8092 Zürich Tel: +41 44 63 27638 E-Mail: michaelt@nari.ee.ethz.ch Web: http://www.nari.ee.ethz.ch/commth/people/show/michaelt