Paper Info
Title
Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields.
Abstract
Reed-Muller codes are some of the oldest and most widely studied error-correcting codes, of interest for both their algebraic structure as well as their many algorithmic properties. A recent beautiful result of Saptharishi, Shpilka and Volk [SSV17] showed that for binary Reed-Muller codes of length n and distance d = 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)). In this paper, we consider the problem of syndrome decoding Reed-Muller codes from random errors. More specifically, given the polylog(n)-bit long syndrome vector of a codeword corrupted in polylog(n) random coordinates, we would like to compute the locations of the codeword corruptions. This problem turns out to be equivalent to a basic question about computing tensor decomposition of random low-rank tensors over finite fields. Our main result is that syndrome decoding of Reed-Muller codes (and the equivalent tensor decomposition problem) can be solved efficiently, i.e., in polylog(n) time. We give two algorithms for this problem: 1. The first algorithm is a finite field variant of a classical algorithm for tensor decomposition over real numbers due to Jennrich. This also gives an alternate proof for the main result of [SSV17]. 2. The second algorithm is obtained by implementing the steps of [SSV17]'s Berlekamp-Welch-style decoding algorithm in sublinear-time. The main new ingredient is an algorithm for solving certain kinds of systems of polynomial equations.
Year
DOI
Venue
2017
10.5555/3174304.3175314
SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, 2018
DocType
Volume
ISBN
Journal
abs/1712.06039
978-1-61197-503-1
Citations 
PageRank 
References 
0
0.34
2
Authors
2
Name
Order
Citations
PageRank
Swastik Kopparty138432.89
Aditya Potukuchi201.01