City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Coding Theory

Since people transmit, process and store huge amount of information, and the hardware is always faulty, we need some means to protect the data against sporadic errors. This need gave birth to the branch of mathematics concerned with methods of reliable data transmission. This area is usually addressed to as \(\emph{coding theory}\). A typical question in this theory is one of the following type: how to use a communication channel where \( 1\% \) of sent bits are lost or corrupted?

The methods developed in coding theory proved to be useful in many problems far beyond error correcting issues, e.g., in communication complexity, in secret sharing, in derandomization of probabilistic algorithms, etc.

In this course we study the basic concepts and classic theorems of coding theory and also discuss some recent achievements in this area. The course is targeted to advanced students studying computer science. We shall specially focus on algorithmic issues of coding theory.

The prerequisites of this course are the basic university courses in probability and linear algebra.

Course Offerings

Semester Branch
spring 2012 Saint Petersburg