Structural and Temporal Information

Speaker : Wojciech Szpankowski
Purdue University
Date: 03/07/2019
Time: 2:00 pm - 3:00 pm
Location: Paris-Rennes Room (EIT Digital)


Shannon’s information theory has served as a bedrock for advances in communication and storage systems over the past five decades. However, this theory does not handle well higher order structures (e.g., graphs, geometric structures), temporal aspects (e.g., real-time considerations), or semantics. We argue that these are essential aspects of data and information that underly a broad class of current and emerging data science applications.
In this talk, we present some recent results on structural and temporal information. We first show how to extract temporal information in dynamic networks (arrival of nodes) from its structure (unlabeled graphs).
We then proceed to establish fundamental limits on information content for some data structures, and present asymptotically optimal lossless compression algorithms achieving these limits for various graph models.


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, analytic combinatorics, network science, random structures, and stability problems of distributed systems.
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, and Gdansk University of Technology, Poland.
He delivered several plenary talks including at ISIT’11, WITMSE’14, CPM’15, AofA16, Knuth80’18, and SODA’19. He has been on editorial boards on many journals including IEEE Trans. Information Theory, TCS, CPC, and ACM Trans. on Algorithms.
Szpankowski 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.
In 2008 he launched the interdisciplinary Institute for Science of Information, and in 2010 he became the Director of the NSF Science and Technology Center for Science of Information.