Skip to content Skip to navigation

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

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:

Speaker: 
Aditya Potukuchi
Location: 
CoRE B (305)
Event Date: 
03/05/2018 - 10:00am
Committee: 
Prof. Swastik Kopparty (Chair), Prof. Shubhangi Saraf, Prof. Jeff Kahn, Prof. Yongfeng Zhang
Event Type: 
Qualifying Exam
Organization: 
Dept. of Computer Science