Wojciech Szpankowski - 2015 Arden L. Bement Jr. Award

Wojciech Szpankowski – 2015 Arden L. Bement Jr. Award

Wojciech Szpankowski is the Saul Rosen Professor of Computer Science at Purdue University. Born in Poland, he received his master’s and doctorate degrees in Electrical Engineering and Computer Science from the Technical University of Gdansk.

He has held several Visiting Professor/Scholar positions, including Stanford, Hewlett-Packard Labs, INRIA, Ecole Polytechnique (France), the Newton Institute, (Cambridge, United Kingdom), Technology University of Gdansk (Poland), and ETH (Zurich). He is a Fellow of IEEE, the Erskine Fellow and 2010 recipient of the Humboldt Research Award. His research interests cover analysis of algorithms, information theory, bioinformatics, analytic combinatorics and stability problems of distributed systems.

Szpankowski also has written two books. “Average Case Analysis of Algorithms on Sequences” is about generating function methodology as applied in the analysis of algorithms. His second book, co-authored with Philippe Jacquet, “Analytic Pattern Matching: From DNA to Twitter,” was published by Cambridge University Press in 2015.

Szpankowski has been a guest editor and an editor of several technical journals, including ACM Transaction on Algorithms, Algorithmica, IEEE Transactions on Information Theory, and Combinatorics, Probability and Computing.

In 2008 he launched the interdisciplinary Institute for Science of Information, whose mission is to extend classical information theory to modern settings, including knowledge discovery and information extraction from massive datasets. He is director of the Purdue Center for Science of Information (CSoI), a National Science Foundation-funded Science and Technology Center in Discovery Park.

Abstract of Lecture

Our current understanding of information dates back to Claude Shannon’s seminal work in 1948, resulting in a general mathematical theory of reliable communication. This theory, broadly referred to as information theory, provided the formal basis for modern digital communication and storage systems.

Analytic information theory addresses problems of information theory using tools of analytic combinatorics. Following Jacques Hadamard’s precept (“The shortest path between two truths in the real domain passes through the imaginary one.”), our work tackles these problems using methods of complex analysis, such as generating functions, Mellin transform, Fourier series, saddle-point method, analytic poissonization and depoissonization, and singularity analysis.

In this talk, after reviewing two main results of Shannon’s work concerning compression and reliable communication, we show how a small modification to the underlying model — to bring it closer to modern-day applications — may render these problems almost intractable. In particular, we present our recent solution to the so-called “noisy constrained capacity” problem, left open since Shannon. This problem finds applications ranging from state-of-the-art storage technologies to computational biology.

In the second part of the talk, we present models and methods for quantifying information embodied in structures. In particular, we present a fundamental lower bound for structural compression and describe a novel algorithm that achieves this lower bound. We demonstrate the significant benefits and broad application scope of our method. We conclude with some challenges for future research.

Research Accomplishments

Professor Szpankowski is known for his foundational work in analytic combinatorics, analysis of algorithms and analytic information theory.

He has made seminal contributions to the emergence of these areas as an organized field of research, evolving from a collection of results on individual problems to a broad and deep discipline with general applicability.

The discipline integrates classical methods of analysis, information, combinatorics and discrete probability to address challenges in data and algorithm analysis. Szpankowski’s scholarship and leadership in this field brought the National Science Foundation’s first Science and Technology Center to Indiana, the Purdue Center for Science of Information (CSoI).

The center, located in Discovery Park, brings the best minds together from across the nation to further the research generated from Shannon’s theory. As director, Szpankowski leads an interdisciplinary team to extend the classical information theory to modern settings through knowledge discovery and information extraction from massive datasets.

Szpankowski has made contributions in three technical areas: stability of computer networks, analysis of algorithms, and information theory (specifically, in data compression).

Stability is a fundamental issue in the design of any distributed system. Typically in an unstable network, the expected number of items (packets, messages, etc.) waiting or being processed/transmitted grows without bound. Thus, it is essential to know the constraints on offered load that guarantee stability, and hence that the network operates within its capacity.

Stability of Markov chains is traditionally studied through the Lyapunov test function approach; however, it is usually hard to construct a good test function in the multidimensional case.

Realizing that, Szpankowski devised a new method for finding stability regions in multidimensional distributed systems. He based his method on a non-Markovian technique combined with stochastic monotonicity and mathematical induction. This allowed him to find stability regions for such important networks as the token passing ring, ALOHA-type systems and others.

Algorithms are at the heart of virtually all computing technologies. Applications range from the infrastructure of computing (e.g., ordering a set of numbers) to highly complex systems (e.g., DNA sequencing). Clearly, the significance of algorithmics can hardly be overstated. Advances take the form of:

• Evaluating the performance of existing algorithms so as to perfect our understanding, and to better inform the choices that need to be made among alternative algorithms.
• Creating algorithms for new applications.
• Expanding the methodology of algorithm design and analysis. Szpankowski made tangible contributions in all three areas. He developed combinatorial and asymptotic methods that allow the classification of data structures into broad categories that are amenable to a unified treatment. These developments have two important consequences for the analysis of algorithms:
• It becomes possible to predict average behavior under more general probabilistic models.
• It becomes possible to analyze more structurally complex systems such as suffix trees and digital trees, the most popular data structures on words.

With respect to new methodology, Szpankowski, with Philippe Jacquet, developed a radically new method of analytic depoissonization to investigate sophisticated algorithms. Furthermore, in his recent work with Michael Drmota, the most popular algorithm design technique known as divide-and-conquer was given a solid mathematical foundation.

Source coding is an area of information theory that provides the foundation for data compression, which is in current widespread use in multimedia compression schemes. A solid understanding of the performance of compression schemes is a key tool in designing provably better information systems.

In information theory, by solving some longstanding open problems (e.g., Wyner-Ziv conjecture, Ziv’s conjecture, redundancy of Lempel-Ziv’78 algorithm, Gutman-Steinberg’s conjecture, Huffman’s and Khodak’s codes redundancy, Csiszar-Shields renewal process redundancy, entropy of hidden Markov processes and capacity of the noisy constrained channel) Szpankowski initiated a novel program, called analytic information theory, that applies analytic combinatorics to the foundation of information theory.

Following Hadamard’s precept, Szpankowski studied information theory problems using techniques of complex analysis such as generating functions, combinatorial calculus, Rice’s formula, Mellin transform, Fourier and Dirichlet series, saddle point methods, analytic poissonization and depoissonization, and singularity analysis.