Project Topics for Essential Coding Theory (MIT 6.440):
Mathematical Theory of Communication (by Claude Shannon). Project unassigned.
Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes
(by Tao Jiang and Alexander Vardy).
the Gilbert-Varshamov bounds for q-ary codes (by Van Vu and Lei
Wu). Project unassigned.
Nonbinary Codes Exceeding the Gilbert - Varshamov Bound for any Fixed
Distance (by Sergey Yekhanin and Ilya Dumer). Project unassigned.
Alon-Boppana Theorems and Error-Correcting Codes (by Joel Friedman
and Jean-Pierre Tillich).
programming bounds for codes via a covering argument (by Michael
Navon and Alex Samorodnitsky). Project
tower of Artin-Schreier extensions of function fields attaining the
Drinfeld-Vladut bound (by A. Garcia and H. Stichtenoth). Project unassigned.
Bounds for List Decoding (by V. Guruswami, J. Hastad, M. Sudan and
to list decodability of linear codes (by V. Guruswami). Project assigned (Minji + Daniel +
- Subspace Polynomials
and List Decoding of Reed-Solomon Codes (by E. Ben-Sasson, S.
Kopparty and J. Radhakrishnan). Project
assigned (Minji + Daniel + Shirley).
to List Decoding Reed-Solomon Codes (by V. Guruswami and A. Rudra).
Decoding of Reed-Solomon Codes is NP-hard (by V. Guruswami and A.
Vardy). Project unassigned.
- Hardness of
approximating the closest vector problem with pre-processing (by
Michael Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth Vishnoi). Project unassigned.
Diophantine Equations over Polynomials and Soft Decoding of
Reed-Solomon Codes (by Michael Alekhnovich). Project half-assigned (Huy + ?).
generators without the XOR lemma (by M. Sudan, L. Trevisan, and S.
Vadhan). Project assigned (Shira
and Pseudorandom Generators (by L. Trevisan). Project assigned (Shubhangi + Jelani).
Expanders and Randomness Extractors from Parvaresh-Vardy Codes (by
Venkatesan Guruswami, Christopher Umans, and Salil Vadhan). Project unassigned.
Hamming Meets Euclid: the Approximability of Geometric TSP and MST
(by Luca Trevisan). Project
3-Query Locally Decodable Codes of Subexponential Length
(by Sergey Yekhanin). Project