Structural, Temporal and Semantic Information

Add to your list(s) Download to your calendar using vCal

• Prof. Wojciech Szpankowski, Purdue University
• Wednesday 16 October 2024, 14:00-15:00
• MR5, CMS Pavilion A.

If you have a question about this talk, please contact Prof. Ramji Venkataramanan.

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), and semantics (quoting Shannon ``the semantic aspects of communication are irrelevant to the engineering problem ’’) While accepting Shannon’s assertion, we observe that since Shannon’s days information has emerged as the currency of our modern technological society.

In this talk, we present some recent results on structural temporal information and semantic 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. Finally, we deal with semantic and study a simple but profoundly important setting in which a sender wants to relay to a recipient a minimal summary of its database of knowledge, written in the language of propositional logic, so that on the receiving side one can answer the same queries as the sender.

—————————— bio sketch——————————

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 Jagiellonian University. Krakow, Poland. 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, in 2015 he was recipient of the naugural Arden L. Bement Jr. Award, and in 2020 he delived the Philippe Flajolet Lecture. He published two books: “Average Case Analysis of Algorithms on Sequences”, John Wiley & Sons, 2001, “Analytic Pattern Matching: From DNA to Twitter” (with P.Jacquet) , Cambridge, 2015, and ``Analytic Information Theory: From Compression to Learning’’ (with (M. Drmota), 2023. 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.

This talk is part of the Information Theory Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Information Theory Seminar
• Interested Talks
• MR5, CMS Pavilion A
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.