Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius

We consider the question of decoding Reed-Muller codes over beyond their list-decoding radius. Since, by definition, in this regime one cannot demand an efficient exact listdecoder, 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 and an efficient approximate decoder, that given query access to a function , 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 ε.