Paper Info
Title
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius.
Abstract
We consider the question of decoding Reed-Muller codes over Fn2 beyond their list-decoding radius. Since, by definition, in this regime one cannot demand an efficient exact list-decoder, we seek an approximate decoder: Given a word F and radii r' > r > 0, the goal is to output a codeword within radius r' of F, if there exists a codeword within distance r. As opposed to the list decoding problem, it suffices here to output any codeword with this property, since the list may be too large if r exceeds the list decoding radius. Prior to our work, such decoders were known for Reed-Muller codes of degree 2, due to works of Wolf and the second author [FOCS 2011]. In this work we make the first progress on this problem for the degree 3 where the list decoding radius is 1/8. We show that there is a constant [Equation] and an efficient approximate decoder, that given query access to a function F : Fn2 → F2, such that F is within distance r = δ − ε from a cubic polynomial, runs in time polynomial in message length and outputs with high probability a cubic polynomial which is at distance at most r' = 1/2− ε' from F, where ε' is a quasi polynomial function of ε.
Year
DOI
Venue
2018
10.5555/3174304.3175313
SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, 2018
Field
DocType
ISBN
Discrete mathematics,Generating function,Combinatorics,Polynomial,Computer science,Quasi-polynomial,Cubic function,Radius,Reed–Muller code,Decoding methods,List decoding
Conference
978-1-61197-503-1
Citations 
PageRank 
References 
0
0.34
9
Authors
2
Name
Order
Citations
PageRank
Pooya Hatami19414.40
Madhur Tulsiani235824.60