News
Lecture 2 slides/recording
Written on 21.04.2021 21:17 by Anand Narayanan
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