Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory

点击翻译按钮获取中文摘要

The interplay between information theory (IT) and computer science (CS)dates back to the founding father of information theory, Claude E.Shannon. Ever since Shannon's work on both information theory andcomputer science, the research in the interplay between IT and CS hascontinued and expanded in many exciting ways. In 2003 the first NSFsponsored Workshop on the IT and CS Interface was held in Chicago,while in 2004 a graduate course on analytic methods in informationtheory and analysis of algorithms was organized at MSRI, Berkeley. Webuild on this momentum and propose to work on problems of informationtheory, combinatorics, and analysis of algorithms. Following Knuth'sand Hadamard's precept, we study such problems using techniques ofcomplex analysis. This program, which applies complex-analytic toolsto information theory, constitutes ``analytic information theory''.This research is focused on some facets of source coding, such as theredundancy rate problem, method of types, entropy evaluation, channelcapacity, and joint channel-source coding. The redundancy rate problemfor a class of sources is the determination of how far the actual codelength exceeds the optimal (ideal) code length, while the method oftypes is a powerful technique in information theory, large deviations,and analysis of algorithms. It is argued that counting types can beaccomplished efficiently by enumerating Eulerian paths (Markov types)or binary trees with a given path length (universal types). Likewise,analysis of the redundancy rate problem for memoryless and Markovsources leads us to interesting generating functions such as treegenerating functions (e.g., arising in counting labeled rooted trees),which are studied extensively in computer science.