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

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

    Codes in new models

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

    Codes for deletion channels

  14. Coding for deletion channels, a survey
  15. Deletion channel capacity for small deletion probabilities

    16. Combinatorics

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

    22. Miscellaneous

  22. Explicit Euclidean sections from expander/Tanner codes
  23. Spatially coupled LDPC codes
  24. Locally dense codes and NP-hardness of minimum distance