Algebraic Coding Theory

Hi all,

on today's class, a student will speak on "Code-based cryptography - McEliece cryptosystem", as a part of the final presentation. 

"Most public-key cryotosystems have a problem - given powerful enough quantum computers, they would become unsecure to use. Therefore it is important to be on the lookout for public-key cryotosystems in the post-quantum era. One of these promising candidates is the McEliece cryotosystems, which is the matter of this talk."

-Anand

Hi all,

today's lecture is pre-recorded and available here.  

recording: https://youtu.be/XB8Bw1HVfAI 

slides: https://drive.google.com/file/d/1pfekq1xqI6xl8qJwYZunUsffxymmRiR4/view?usp=sharing

There will be no lecture session during the regular class time. Instead, please email me if you have questions. 

References : 

Cohen-Haeupler-Schulman explicit tree codes 

https://dl.acm.org/doi/10.1145/3188745.3188928

Decoding

https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.81

Conjectural tree codes

https://eccc.weizmann.ac.il/report/2020/141/

Triangular block matrices and tree codes 

https://arxiv.org/pdf/2012.03013.pdf

-Anand

Hi all,

lecture 12 recording/slides are here

https://youtu.be/WKeHKmeAw4U

https://drive.google.com/file/d/1NbQ7Q3qYOgBw2tcwkzMZaShQfju0Crke/view?usp=sharing

References : 

Cohen-Haeupler-Schulman explicit tree codes 

https://dl.acm.org/doi/10.1145/3188745.3188928

For a proof of the Gessel-Viennot lemma, see chapter "lattice paths and determinants" in "Proofs from the book"

https://link.springer.com/book/10.1007/978-3-662-57265-8

-Anand

Hi all,

on today's class, two students will speak on the Braverman-Rao protocol, as a part of their final presentation. 

"Today we are going to describe a coding scheme by Braverman and Rao that has an optimal noise resilience while maintaining a constant rate. They proved the possibility to encode any communication protocol between two parties so that the protocol is successful even if a fraction of all symbols transmitted by the parties are corrupted adversarially, ¼-ε to be exact. We are going to have a quick recap on tree codes and then try to motivate you regarding the need of such protocol and try to explain it to you as simply as possible."

-Anand

Hi all,

lecture 10 slides/recording are here.

https://youtu.be/2jOAsJ4Re8s

https://drive.google.com/file/d/1lDAHJw7nbbUSVIvp61B1AN2qscRKa5mk/view?usp=sharing

References: 

Schulman's paper introducing interactive coding and tree codes

https://ieeexplore.ieee.org/document/556671

A more recent survey

https://www.eng.biu.ac.il/~gellesr/survey.pdf

The existence proof for tree codes on the lecture closely follows Pudlak

 https://arxiv.org/abs/1310.5684

-Anand

Hi all,

So far, we learnt to "speak in the presence of noise" using classical error correcting codes.

Today, we will begin to learn to "converse in the presence of noise" using tree codes.  

We will introduce tree codes and show that good tree codes exist. Over the remaining lectures, we will explicitly construct "almost" good tree codes. Here on, there will be just as much combinatorics/graph theory as algebra/geometry. If you missed a few of the previous lectures, this is a good time to hop back in.

-Anand

Hi all,

lecture 9 recording and slides are here

https://drive.google.com/file/d/19IX0BBAg5heKHF4Mp765sjoylY2e2fY7/view?usp=sharing

https://youtu.be/1zjKZZf-NEI

References:

Sipser-Spielman expander codes

http://www.cs.yale.edu/homes/spielman/PAPERS/expandersIT.pdf

Spielman super concentrator codes

http://cs-www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf

Guruswami-Umans-Vadhan bipartite expander

https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf

-Anand

Hi all, 

Lecture 8 recording and slides are here

https://youtu.be/mjhbDi4Vruo

https://drive.google.com/file/d/1kx7j773AVtBtdrMlgDl2WDEepzE10K9H/view?usp=sharing

For PCPs see chapter 18-19 of the Arora-Barak book

https://theory.cs.princeton.edu/complexity/book.pdf

Historic notes on the PCP theorem

https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf

-Anand

Hi all!

Lecture 7 recording and slides are here

https://youtu.be/1QRaJ3AxHzg

https://drive.google.com/file/d/1XN6bB-NVG9YHbSZdsakYoDj3vQJKq8P6/view?usp=sharing

Blum-Luby-Rubinfeld linearity test

https://www.sciencedirect.com/science/article/pii/002200009390044W

Fourier analytic proof

https://madhu.seas.harvard.edu/papers/1995/bchks-conf.pdf

-Anand

Hi all,

On today's lecture we start with a gentle/infomal introduction to Probabilistic Checkable Proofs PCPs and their relation to NP. Then we build tools from algebraic coding theory that played a part in the original proof of the PCP theorem. The main tool will be the Blum-Luby-Rubinfeld linearity test. We conclude with low degree testing (local testing of Reed-Muller codes). Most of what we discuss today is new and understandble even if you missed the past few classes.

Next class: We will study PCPs with greater care and prove a very weak version of the PCP theorem with a long witness.  

-Anand

Hi all,

This week, instead of a lecture, there will be a one-on-one session with students discussing prospective final project reports/presentations. 

Those of you wanting to take the final project/presentation, please send me an email, to secure a time slot sometime between 14-16 hr this wedensday.

If you want to do the project in small groups, but don't have teammates, send me an email and I will try to match you up.

The sessions are informal, discussing your background and interests in the course. We can try to identify topics and papers best suited to you.

In the next few weeks, there are lots of graph theoretic codes and interactive protocol coding coming up. Look up the course plan and also go through the lectures, if you missed them, to know what excites you.

-Anand

Hi all,

Lecture 6 recording and slides are here

https://youtu.be/0Nv_7fg9QfM

https://drive.google.com/file/d/12EzCqzaZBsq-GS_R7UVkkwWTYwwqJ80d/view?usp=sharing

For Reed-Muller codes, the textbook is a good starting point.

For Reed-Muller local decoding on lines, see Yekhanin's book, chapter 2

http://people.csail.mit.edu/dmoshkov/courses/codes/LDC_now.pdf

Moshkovitz's proof of Schwartz-Zippel

https://eccc.weizmann.ac.il//report/2010/096/

For a probabilistic proof by induction and use in polynomial identity testing, see Saxena's survey

https://www.cse.iitk.ac.in/users/nitin/papers/pit-survey09.pdf

Tutte's matrix and perfect matching proof, see page 2 of

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.486.3616&rep=rep1&type=pdf

Agarwal-Biswas primality proving (see also Saxena's survey above)

https://www.cse.iitk.ac.in/users/manindra/algebra/identity.pdf

-Anand

Hi All,

Today we will introduce Reed-Muller codes and prove their distance using the Schwartz-Zippel lemma. Then we study a local decoding algorithm for Reed-Muller codes. 

We also take a few fun deviations outside coding theory. We apply the Schwartz-Zippel lemma to polynomial identity testing. In particular, simple algorithms for

i) finding perfect matchings in graphs

ii) and testing if a given number is a prime. 

Next class: Application of Reed-Muller codes to property testing/PCPs etc..

-Anand

Hi all,

The recording/slides of lecture 5 are here

https://youtu.be/hu_rdz8dHf8

https://drive.google.com/file/d/1tHa6H6JzU6a5UCHFUDxWgxDzicfREjns/view?usp=sharing

Shamir's secret sharing is here

http://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf

There was a question on the extension to MDS codes, it is due to McEliece and Sarwate. See also the introduction in Massey's extension to all linear codes, with the reconstruction/secrecy expressed in terms of the dual code. 

https://lihaoxu.eng.wayne.edu/Courses/CSC7270/Note/p583-mceliece.pdf

http://www.isiweb.ee.ethz.ch/papers/arch/mass-1993-3.pdf

The electronic voting protocol is due to Schonemaker

https://www.win.tue.nl/~berry/papers/crypto99.pdf

See also the zero knowledge chapter 25 in Nigel Smart's book "Introduction to cryptography". He has made an online copy free.

The use of algebraic geometry codes for secret sharing is due to Chen and Cramer

https://www.iacr.org/cryptodb/archive/2006/CRYPTO/1894/1894.pdf

-Anand

 

 

Hi all,

On today's lecture we will study an important application of algebraic coding theory to cryptography: secret sharing. We then deploy secret sharing to build a certifiable distributed voting scheme where the votes are kept secret while being counted. 

We will go through secret sharing at an easy pace, small bias sets (advertised in the course description) will be deferred to a later lecture.

-Anand

Hi All,

The most difficult (algebraic-geometric) part of the course is done!

From here on, the lectures will be elementary, self contained and catered towards computer science applications. 

Recoding:

https://www.youtube.com/watch?v=IHOSkTq8O2c

Slides:

https://drive.google.com/file/d/1bRqSbvgYmsVCQZvdFWXMJZO2A2UcTpWU/view?usp=sharing

Our lecture may be the easiest way to get started on Garcia-Stichtenoth towers, all the other expositions target advanced mathematics audiences. The best such sources are

1.) Stichtenoth's book (see course description) and

2.) https://link.springer.com/article/10.1007/BF01884295

For fast computation of Riemann-Roch spaces of curves over finite fields:

1) For plane curves:

 https://www.sciencedirect.com/science/article/pii/S0747717184710637

2.) For curves in higher dimensional ambient space:

http://www.staff.uni-oldenburg.de/florian.hess/publications/rr.pdf

3.) For Garcia-Stichtenoth towers:

https://ieeexplore.ieee.org/document/923746

https://ieeexplore.ieee.org/document/945244

For nearly linear time codes beating the Gilbert-Varshamov bound

https://ieeexplore.ieee.org/document/8770116

(there is a free version on arxiv or email me, I can send you the paper for free as an authour).

Decoding:

Shokrollahi-Wasserman algorithm.

https://dl.acm.org/doi/10.1145/276698.276753

-Anand

Hi All,

This wednesday, we will complete our discussion of algebraic geometry codes beating the Gilbert-Varshamov bound. The lecture should only take an hour and will likely end at 15 hr. Please review last week's lecture to be comfortable with the upcoming lecture.

From 15-16 hr, I would like to discuss final project ideas with students individually or in small groups of two or three. There will be lots of such sessions throughout the term. If you/your group would like a time slot this week, please send me an email. It will be a short 10-15 min informal discussion, trying to identify finals topics that might excite you.

-Anand 

 

Hi All,

Lecture 3 recording and slides are up. Those who missed the class, please listen to the lecture before next week. Next week's lecture will not be self contained and will depend on an understanding of today's lecture. 

Recording:

https://youtu.be/AGzRBS04n4A

Slides:

https://drive.google.com/file/d/1V93QBCpNRrTRG99Rkf5rrU-RsqeRAAOM/view?usp=sharing

The main reference is Stichtenoth's book "Algebraic function fields and codes", listed in the course description.

Silverman's text book, "Arithmetic of elliptic curves" is another excellent source for projective coordinates, curves, function fields, divisors, Riemann-Roch etc..

After next week's lecture, I shall list pointers to applications and prospective project topics on algebraic geometry codes.

-Anand

Hi All, 

A reminder that we will use the same zoom link for all our lectures from here on.

https://us02web.zoom.us/j/88142783308?pwd=aXFyckk0ajI2MjVDV2FBK3FRUFpIdz09

Today, we will study algebraic geometry codes from plane curves. It involves quite a bit of number theory that is typically not covered in computer science classes. Please be patient, towards the end of the lecture, I shall summarize the constructions in simple terms! 

-Anand

Hi All,

Lecture 2 slides: https://drive.google.com/file/d/1DF4HvbuMnWDph3nZ9WUw6anF4fh4Xqe8/view?usp=sharing

Lecture 2 recording: https://www.youtube.com/watch?v=6_mJW7lFK2k

The online book for the course is an excellent reference for the topics covered.

A few other relevant references:

1. Multipoint evaluation: 

Borodin and Moenck: Fast modular transforms.

http://www.cs.toronto.edu/~bor/Papers/fast-modular-transforms.pdf

There are also computer algebra text books with detailed coverage of multipoint evaluation:

von zur Gathen and Gerhard, Modern Computer Algebra or https://hal.archives-ouvertes.fr/AECF/ (the later is free, but only in french).

2. List decoding algorithms.

Sudan: http://madhu.seas.harvard.edu/papers/1996/reeds-journ.pdf

Guruswami-Sudan: https://madhu.seas.harvard.edu/papers/1998/venkat-conf.pdf

Guruswami's thesis: https://dspace.mit.edu/handle/1721.1/8700

Average list size analysis: https://tda.jpl.nasa.gov/progress_report/42-153/153F.pdf.  (See appendix D)

Alekhnovic's fast decoding: https://www.math.ias.edu/~misha/papers/diophant.ps

Displacement algorithms for inverting structured matrices: https://www2.math.uconn.edu/~olshevsky/papers/shokrollahi_f.pdf

-Anand

 

Hi All,

Here is a stable zoom link that should work for every lecture Wednesdays 14-16 hr from here on. 

Please bookmark it.

Join Zoom Meeting
https://us02web.zoom.us/j/88142783308?pwd=aXFyckk0ajI2MjVDV2FBK3FRUFpIdz09

Tomorrow, we quickly recap Reed-Solomon codes and study how to encode and decode them. If you've scanned a QR-code on your mobile phone/handy and wondered what the mathematics behind those pictures are, tune in! Lots of algorithms and very little counting. 

Anand

 

Hi All, 

Lecture 1 recording and slides are here

https://youtu.be/kSJQ1PRfD9o

https://drive.google.com/file/d/1z5MZQ0zxNZAzyTD8L6o4tybDKj3BMo3k/view?usp=sharing

Supplementary/Tangential material:

For Golay code constructions, please see

https://www.win.tue.nl/~aeb/2WF02/Witt.pdf

The easiest constructions are using the icosahedron and quadratic residues. We will cover the later in next week's class.

For construction of the Leech lattice from Golay codes, see the last two pages of

http://www.ams.org/notices/200408/fea-pfender.pdf

If you are interested in lattice sphere packing analogues of codes for your project, email me for directions.

Anand

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