Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields

Aditya Potukuchi, Rutgers University

Location:  CoRE 301
Date & time: Wednesday, 15 November 2017 at 11:00AM - 12:00PM

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.

Joint work with Swastik Kopparty


Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.