DIMACS Theoretical Computer Science Seminar

Title: Reed-Muller Codes with Respect to Random Errors and Erasures

Speaker: Amir Shpilka, Technion

Date: Wednesday, October 8, 2014 11:00-12:00pm

Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ


In TCS we usually study error correcting codes with respect to the Hamming metric, i.e. we study their behaviour with respect to worst case errors. However, in coding theory a more common model is that of random errors, where Shannon’s results show a much better tradeoff between rate and decoding radius.

We consider the behaviour of Reed-Muller codes in the Shannon model of random errors. In particular, we show that RM codes with either low- or high-degree (n^1/2 or n-n^1/2, respectively), with high probability, can decode from an 1-r fraction of random erasures (where r is the rate). In other words, for this range of parameters RM codes achieve capacity for the Binary-Erasure-Channel. This result matches experimental observations that RM codes can achieve capacity for the BEC, similarly to Polar codes. We also show that RM-codes can handle many more random errors than the minimum distance, i.e. roughly n^d/2 errors for codes of degree n-d (where the minimum distance is only 2^d).

We show that the questions regarding the behaviour of Reed-Muller codes wrt random errors are tightly connected to the following question. Given a random set of vectors in {0,1}^n, what is the probability the their d’th tensor products are linearly independent? We obtain our results by giving answer to this question for certain range of parameters.

Based on a joint work with Emmanuel Abbe and Avi Wigderson.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/