# Information theory

# Information theory

Wed-Fri 15h-17h

from March 4, 2015

–

Room 101, Facultat de Matemàtiques i Estadística, UPC

The aims of this course are to review the fundamental principles and methods of information theory. Since Shannon’s landmark work in 1948, information theory has been at the core of information processing systems. Nowadays, information theory finds wide applications in

areas such as communications engineering, probability theory, statistics, physics, computer science, mathematics, economics, bioinformatics and computational neuroscience.

Wed-Fri 15h-17h

from March 4, 2015

–

Room 101, Facultat de Matemàtiques i Estadística, UPC

The aims of this course are to review the fundamental principles and methods of information theory. Since Shannon’s landmark work in 1948, information theory has been at the core of information processing systems. Nowadays, information theory finds wide applications in

areas such as communications engineering, probability theory, statistics, physics, computer science, mathematics, economics, bioinformatics and computational neuroscience.

Albert Guillen i Fàbregas, ICREA (UPF)

Alfonso Martinez (UPF)

Andreas Winter, ICREA (UAB)

##### Summari

The aims of this course are to review the fundamental principles and methods of information theory. Since Shannon’s landmark work in 1948, information theory has been at the core of information processing systems. Nowadays, information theory finds wide applications in

areas such as communications engineering, probability theory, statistics, physics, computer science, mathematics, economics, bioinformatics and computational neuroscience.

The course will cover source coding, rate distortion, data transmission, and multiple-user information theory. The course will not only review the main results of information theory, but will also describe proof methodologies and illustrate the key tradeoffs between the underlying system parameters. In the last third or quarter of the course, quantum information theory will be discussed, which is the generalization of information theory to systems that are described by quantum mechanics, exhibiting a large range of new phenomena, while giving rise to a theory that has at least partially strong similarity to “classical” information theory. No prior knowledge of quantum physics is required.

##### Contents

**Data Compression**. Discrete memoryless sources. Lossless data compression. Entropy. Lossy data compression: rate distortion. Computation of rate distortion region.**Data Transmission**. Discrete memoryless channels. Channel capacity (typical sequences). Computation of channel capacity. Error exponents (optimal decoding). Joint source-channel coding (lossless and lossy, separation vs oint). Hypothesis testing and lower bounds to error probability. Gaussian-noise channels. Differential entropy. Parallel channels.**Multiple User Information Theory**. Multiple User Source Coding. Multiple Access Channel. Broadcast Channel. Relay and Interference channels.**Basics of finite quantum systems**. Quantum states as a new kind of information. No-cloning theorem. Teleportation.**Quantum data compression**. Von Neumann entropy. Typical subspace.**Quantum data compression with side information at the decoder**. Entanglement distillation. Quantum channel coding; quantum capacity.

##### Bibliography

For Block B we follow

[T. Leinster: Basic Category Theory, CUP 2014]. Additional references include:[E. Riehl: Category Theory in Context, CUP 2014] [S. Awodey: Category Theory, OUP 2010], and [F. W. Lawvere & R. Rosebrugh: Sets for Mathematics, CUP 2003] (for B3).

For Block A:

A1: [J. Baez & M. Stay: Physics, Topology, Logic and Computation: a Rosetta Stone, 2009] [J. Kock: Frobenius algebras and 2D topological quantum field theories, CUP 2004]. [C. Heunen & J. Vicary: Categorical Quantum Mechanics, CUP, forthcoming,prefinal version available].

A2: [F. Borceux: Handbook of Categorical Algebra: Volume 2, CUP 1994] [F. W. Lawvere: Metric spaces, generalized logic, and closed categories, 1973, TAC Reprint 2002] [T. Leinster: The Magnitude of Metric Spaces, Documenta Math. 2013].

A3: [S. Awodey: Category Theory, OUP 2010] [T. Leinster: Higher operads, higher categories, CUP 2003].

A4: [M. La Palme Reyes, G. Reyes and H. Zolfaghari: Generic figures and their glueings: A constructive approach to functor categories. Polimetrica, 2004] [D. Spivak: Category Theory for the Sciences, MIT Press 2014].

A5: [A. Joyal: Une théorie combinatoire des séries formelles, Adv. Math. 1981] [J. Baez, J. Dolan: From finite sets to Feynman diagrams, Mathematics unlimited, 2001] [J. Kock: Notes on polynomial functors, manuscript, 2009].

A6: [R. Brown: Topology and Groupoids, Booksurge 2006].