Algebraic Coding Theory Anand Narayanan

Registration for this course is open until Friday, 16.04.2021 23:00.

News

13.04.2021

Lecture 1 zoom link

Hi All,

Welcome to algebraic coding theory. Zoom link to the first lecture follows.

Topic: Coding Theory Lecture 1
Time: Apr 14, 2021 02:00 PM Amsterdam, Berlin, Rome, Stockholm, Vienna

Join Zoom Meeting
... Read more

Hi All,

Welcome to algebraic coding theory. Zoom link to the first lecture follows.

Topic: Coding Theory Lecture 1
Time: Apr 14, 2021 02:00 PM Amsterdam, Berlin, Rome, Stockholm, Vienna

Join Zoom Meeting
https://us04web.zoom.us/j/78711944939?pwd=Tll3bUVSblhiV053RTY1VitkZEVqUT09

Meeting ID: 787 1194 4939
Passcode: 0kzQds

 

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/Riemann-Roch) 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 14-16 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.

Library link

 

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators