0368.4611

Seminar on error correcting codes

Fall 2008.

Lecturer: Amnon Ta-Shma

When and where:  Sundays, 13:10-15:00. Schreiber 309.

Grading: Based on participation in class and paper presentation.

Links:

Madhu Sudan	Essential Coding Theory
Luca Trevisan	Pseudorandomness and Combinatorial Constructions
Luca Trevisan	Coding Theory and Complexity
Atri Rudra	Error Correcting Codes: Combinatorics, Algorithms and Applications

Lectures:

Date	Speaker	Topic	Reference
(1) 2.11.08	Amnon Ta-Shma	Introduction. Basic definitions. Simple examples. Overview of seminar.
(2) 09.11.08	תומר לוינבוים Slides	Asymptotically good binary code with efficient encoding. Justensen code.	[Sudan, Lecture 6], [Trevisan-ECC, Lectures 1,2], [Rudra, lecture 25]
(3) 16.11.08	Berlekamp Welch unique decoding algorithm ברק פנחס Guruswami Sundan - ppt Class notesClass notes Madhu's slides. See slide 29 (56 of 91).	Belekamp Welch algorithm for unique decoding RS.	[Sudan, Slides, Lecture 10], [Trevisan-ECCC, Lect 1], [Rudra, lecture 27]
		Sudan's algorithm for list-decoding RS. Guruswami-Sudan algorithm.	Madhu Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound Venkatesan Guruswami ,Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes [Rudra, lectures 37,38,39]
(4) 23.11.08
(5) 30.11.08	ינון פלד Slides	2 and 3 Local decoding.	Klim Efremenko: 3-Query Locally Decodable Codes of Subexponential Length
(6) 7.12.08	אמנון אהרונסון Slides	Local list-decoding binary codes	The Goldreich-Levin Theorem: Local list-decoding the Hadamard code. [Trevisan -PRG, lecture 8] Three XOR-Lemmas, an Exposition - by Oded Goldreich
(7) 14.12.08 21.12.08	דניאל שחף Slides	Local list-decoding RM codes	[Sudan, Lecture 15], Trevisan ECCC, Lect 6] Madhu Sudan, Luca Trevisan, Salil Vadhan, Pseudorandom generators without the XOR Lemma
28.12.08	לא תערך פגישה	חנוכה
(8) 4.1.09	אפרת בנק Slides	Parvaresh Vardy codes	Farzad Parvaresh, Alexander Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time. Rudra, lectures 40,41,42. Draft.]
11.1.09	לא תערך פגישה
(9) 18.1.09	רועי כשר Notes	Unbalanced condensers from Parvaresh Vardy codes	V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
25.1.09	לא תערך פגישה
(10) 1.2.09	אמיר לוי	LDPC codes. Expander codes.	[Sudan, Lecture 16], Trevisan ECCC, Lect 7]
		Kakaya sets and mergers	Zeev Dvir. On the size of Kakeya sets in finite fields. Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers and old extractors.
		Back to binary codes: eps-bias. upper and lower bounds. constructions.	Joseph Naor and Moni Naor. Small-bias Probability Spaces: efficient constructions and Applications Noga Alon, Oded Goldreich Johan Hastad and Rene Peralta, Simple Constructions of Almost k-wise Independent Random Variables
		Asymptotically good, linear time encodable and decodable binary codes.	[Sudan, Lecture 17], Trevisan ECCC, Lect 8]