Seminar Details
Syndrome Decoding of Reed-Muller Codes and Tensor Decomposition over Finite Fields
- Start Date: November 15, 2017
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Aditya Potukuchi - Rutgers University
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- Abstract:
In this talk, we will look at decoding Reed-Muller codes beyond their minimum distance when the errors are random (i.e., in the binary symmetric channel). A recent beautiful result of Saptharishi, Shpilka and Volk showed that for binary Reed-Muller codes of length n and degree n - O(1), one can correct polylog(n) random errors in poly(n) time (which is well beyond the worst-case error tolerance of O(1)). We will see two efficient algorithms as well as a different proof of the same result, where the decoding is done given the polylog(n)-bit long syndrome vector of the corrupted codeword:
1. The first is via. a connection to the well-studied \`tensor decomposition problem'.
2. The second via. a reduction to finding all common roots of a space of low degree polynomials, which is also of independent interest.