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


Abstract:

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/