Syllabus
Information Theory
· Information, entropy, mutual information
· Relative information and its properties
· Data compression - Shannon-Fano code, Huffman code
· Kolmogorov complexity, Kolmogorov information, symmetry of Kolmogorov information
Error-Correcting Codes
· Data transmission over a noisy channel, channel capacity, Shannon's theorems
· Non-explicit codes
· Hamming codes
· Reed-Solomon codes, Berlekamp-Welch algorithm
Communication Complexity
· Model of communication complexity
· Deterministic complexity, combinatorial rectangles, examples
· Probabilistic protocols, public and private random bits
· Non-deterministic protocols
· Application: analysis of data structures
Annotation
The course covers the fundamental concepts of information theory, error-correcting codes and communication complexity.