Possible project topics, Coding Theory, Fall 2014

Venkatesan Guruswami

The final course project, done in teams of two (or solo if preferred), involve
  1. A 25 minute short presentation in class that clearly explains the topic/problem setting/model considered in the paper; the major mathematical challenges driving the topic; the specific results obtained in the paper(s) studied (highlighting any salient questions that are still open); and a glimpse of the key construction ideas/proof techniques in the paper.

  2. An accompanying term paper (about 10-15 pages long), structured similarly to the talk, but going into more details and formal statements.
(I've tried to mostly suggest papers below for which the above tasks will not be onerous and in fact pleasant to do.)

List of suggested papers/topics

(these are in no particular order; you are also welcome to pick a topic/paper not listed below, but please run it by me first)

    Local decoding/testing

  1. High-rate locally correctable expander codes
  2. Locally testable codes and Reed-Muller based small set expanders (Section 4 contains this connection)
  3. Local testing of binary Reed-Muller codes
  4. Local list-decoding and testing of sparse, unbiased codes
  5. Reed-Muller code based hardness amplification (Relevant material is in Section 4)
  6. Locally recoverable codes
  7. Towards lower bounds on locally testable codes via density arguments
  8. Algebraic coding

  9. List decoding binary Reed-Muller codes
  10. Small-bias sets from Hermitian codes
  11. Explicit subspace designs from algebraic codes

    Codes in new models

  12. Codes for computationally bounded channels
  13. Non-malleable codes: their capacity
  14. Interactive information and coding theory (A survey)

    Codes for deletion channels

  15. Coding for deletion channels, a survey
  16. Deletion channel capacity for small deletion probabilities
  17. Combinatorics

  18. Proof of MDS conjecture for prime fields
  19. On Delsarte's linear programming bounds for binary codes
  20. Zero-error information theory (A survey)
  21. Repeated communication and Ramsey Graphs
  22. Zero error list-decoding capacity (See references in this paper for historical context)
  23. On the List-Decodability of Random Linear Codes
  24. Miscellaneous

  25. Explicit Euclidean sections from expander/Tanner codes
  26. Spatially coupled LDPC codes
  27. Locally dense codes and NP-hardness of minimum distance