News
13.04.2021

Lecture 1 zoom linkHi All, Welcome to algebraic coding theory. Zoom link to the first lecture follows. Topic: Coding Theory Lecture 1 Join Zoom Meeting Hi All, Welcome to algebraic coding theory. Zoom link to the first lecture follows. Topic: Coding Theory Lecture 1 Join Zoom Meeting Meeting ID: 787 1194 4939 
Algebraic Coding Theory
(Click here for a detailed course plan.)
The course is an invitation to algebraic coding theory, guided by a few excursions through applications arising in complexity theory. We start with Hamming's classical problem. A sender wants to transmit a message reliably over an erroneous channel by encoding it into a longer string called a codeword. The receiver must recover the message provided the number of errors inflicted on the codeword, which may be adversarial is bounded. We study i) bounds on the tradeoff between rate of information transmission and fraction of errors tolerated and ii) explicit construction of codes from algebraic objects (such as polynomials over finite fields and their generalisations). En route, we explore a few applications in complexity theory including property testing, secret sharing, unbalanced expanders and small bias sets. We then study interactive communication, where multiple players talk for several rounds towards a common objective. Its intricacies are already captured in two honest players playing blindfold chess over a noisy channel. How does one encode the moves such that even if a constant fraction of the transmissions are in error, the state of the game is recovered ? One may try to employ classical codes for each move, but then even a single erroneous transmission may destroy the whole game. Further one does not know the moves in advance. Schulman introduced online/causal versions of error correcting codes, called tree codes to address this. Our main focus is on exciting recent advancements due to Cohen, Haeupler and Schulman: explicit tree codes!
Grading: An end of term report (60%) and oral presentation (40%) on a relevant topic chosen by the student will account for most of the grading. Regular attendance is encouraged and the classes will be live.
Prerequisites: The course is open to both MSc and BSc students. Familiarity with algorithms and complexity theory is assumed, to the extent covered in "Grundzüge der Algorithmen und Datenstrukturen" and "Grundzüge der Theoretischen Informatik". Students must be comfortable with basic linear algebra, discrete probability and graph theory covered in "Mathematik für Informatiker I  II". Finite fields feature prominently. No familiarity with finite fields is assumed, they will be developed as necessary. Arithmetic algebraic geometry (curves over finite fields/RiemannRoch) plays a role, but we take an elementary approach assuming no prior knowledge. "Complexity Theory" and "Computer Algebra" are useful but neither course is required.
Schedule: 2h lecture (Wednesdays 1416 hr) + 2h exercise (Questions/discussion on the week's lecture or reading papers covered) per week.
Books: There are no required text books. Please see the course plan for a list of supplementary papers and books.