Finite-Length Information Theory

European Research Council, Starting Grant 2011-2016

Shannon's Information Theory establishes the fundamental limits of information processing systems. A concept that is hidden in the mathematical proofs most of the Information Theory literature, is that in order to achieve the fundamental limits we need sequences of infinite duration. Practical information processing systems have strict limitations in terms of length, induced by system constraints on delay and complexity. The vast majority of the Information Theory literature ignores these constraints and theoretical studies that provide a finite- length treatment of information processing are hence urgently needed. When finite-lengths are employed, asymptotic techniques (laws of large numbers, large deviations) cannot be invoked and new techniques must be sought. A fundamental understanding of the impact of finite-lengths is crucial to harvesting the potential gains in practice. This project is aimed at contributing towards the goal of providing a unified framework for the study of finite-length Information Theory. The approach in this project will be based on information- spectrum combined with tight bounding techniques. The results of this project will be of benefit to areas such as communication theory, probability theory, statistics, physics, computer science, mathematics, economics, bioinformatics and computational neuroscience.