- Lectures
- Omar Fawzi
- Tuesdays 8:00 to 10:00
- Amphi B

- Tutorials
- Dewi Sintiari and Mateusz Skorma
- Wednesdays 8:00 - 10:00

- Definition and properties of entropy functions
- Data compression
- Shannon's noisy coding theorem
- Applications of information theory to combinatorics, cryptography, complexity theory
- Error correcting codes: Definitions, properties and examples
- Applications of error correcting codes

- [CT] Elements of Information Theory
- [Mac] Information Theory, Inference and Learning Algorithms
- [PW] Lecture notes on Information Theory
- [GRS] Essential Coding Theory
- [Sen] Introduction a la theorie de l'information

- A final exam
- One midterm exam
- Homeworks (every 1 or 2 weeks)
- Bonus: Small project, such as writing a wikipedia article

Date | Topic | References |

Sep 10th | Admin. Overview of the fundamental problem of noisy channel coding. Definition of entropy. |
Ch 1 of [Mac], Ch 2 of [CT], Shannon's paper |

Sep 17th | Conditional entropy, mutual information, relative entropy. Data compression, variable-length lossless compressor. |
Ch 8.1 of [PW], Ch 4 of [Mac], Ch 2,3,5 of [CT] |

Sep 24th | Continuing variable-length coding. Prefix codes, Kraft's inequality, H(X) < L(C) < H(X)+1. Fixed-length compression, general bound in the size of the smallest set with prob >= 1-delta. |
Ch 8.2 of [PW], Ch 5,6 of [Mac], Ch 5 of [CT], Ch 9.1 of [PW] |

Oct 8th |
Shannon's source coding theorem Universal compression: arithmetic coding. See here for more details on compression |
Ch 16.1 of [PW], Ch 6 of [Mac] |

Oct 9th |
Channel coding: Information capacity of a channel. Additivity of information capacity for independent channels. Converse bounds |
Ch 16.3 [PW], Ch 7 of [CT]. |

Oct 16th | Achievability bounds. Shannon noisy coding theorem. |
Ch 16.4 [PW], Ch 7 of [CT] |

Oct 22nd | Zero-error channel coding. Lovasz theta function. Information theory and combinatorics. |
Entropy and counting |