Local list decoding of Reed–Muller codes along lines with advice #
Let p be a polynomial of total degree at most d in m variables over a field F with q
elements, and let g agree with p on a set A of a points, a small fraction of the
Q = q ^ m points. Local list decoding [STV01] recovers p(x) at most points
x by decoding g along the line through x and a fixed point z, using the advice p(z) to
single out p among the polynomials that agree with g on the line.
The decoder Cslib.Code.lineListDecode g d D z a x parametrizes the line by
t ↦ x + t • v, where v is z - x scaled so that its first nonzero entry is 1
(Cslib.LinearAlgebra.firstNonzero); then z = x + c • v for c the first nonzero entry of
z - x. It runs Sudan decoding with the hint a at c on the restriction of g to the line
(Cslib.Code.hintDecode). The direction v and the received word depend only on x and the line,
not on the position of z on it, so the hint position c is uniformly distributed over F ∖ {0}
given the line.
Two things can go wrong for a pair (x, z): the line can have at most D agreements, or the hint
position can be one of the at most D - d bad positions of Cslib.Code.card_hintDecode_ne_le.
Points of a random line are pairwise independent and uniform, so the number N of agreements on
the line through a random point in a random direction has mean μ = q * a / Q and variance at most
μ, and Chebyshev's inequality bounds the first event
(Cslib.Code.card_filter_lineAgree_le_mul_sq_le). The second has probability at most
(D - d) / (q - 1) given the line. Averaging over z
(Cslib.Code.exists_card_lineListDecode_ne_le), some advice point z makes the decoder, with the
advice p(z), correct at all but
1 + (q * a * (Q - 1) / (μ - D) ^ 2 + Q * (Q - 1) * (D - d) / (q - 1)) / Q points.
Main definitions #
Cslib.Code.lineAgree: the number of points of a line in a set.Cslib.Code.lineListDecode: the local list decoder with advice.
Main results #
Cslib.Code.card_filter_lineAgree_le_mul_sq_le: random lines sample a set well.Cslib.Code.lineListDecode_eq: the decoder is correct on good lines and hint positions.Cslib.Code.exists_card_lineListDecode_ne_le: local list decoding of Reed–Muller codes.
References #
- [M. Sudan, L. Trevisan, S. Vadhan, Pseudorandom generators without the XOR lemma] [STV01]
- S. Arora, B. Barak, Computational Complexity: A Modern Approach, Chapter 19
Random lines sample well #
Random lines sample a set well. Over all points x and nonzero directions u, the
number of pairs for which the line t ↦ x + t • u has at most D points in A is at most
q * a * (Q - 1) / (μ - D) ^ 2, where a = #A, Q = q ^ m and μ = q * a / Q > D is the mean
number of points of a line in A.
The decoder #
The local list decoder with advice. To decode at x with advice a at z: parametrize
the line through x and z as t ↦ x + t • v, with v the normalization of z - x, and run
Sudan decoding with the hint a at the position c = firstNonzero (z - x) of z on the
restriction of g to the line.
Instances For
Scaling the direction by a nonzero constant does not change the number of points of a line in a set.
The decoder at a pair of points. For z ≠ x, with c = firstNonzero (z - x) and
v = c⁻¹ • (z - x), the decoder with advice p z is Sudan decoding with the hint p (x + c • v)
at c on the line t ↦ x + t • v.
Local list decoding of Reed–Muller codes, a variant of [STV01]. Let
p be a codeword of the Reed–Muller code of degree d ≥ 1 in m variables over a field with q
elements, Q = q ^ m, and let g agree with p on a points. Let D < q be such that there
are more than q monomials of (1, d)-weighted degree at most D, and suppose
D < μ = q * a / Q. Then for some advice point z, the decoder lineListDecode g d D z (p z)
computes p at all but
1 + (q * a * (Q - 1) / (μ - D) ^ 2 + Q * (Q - 1) * (D - d) / (q - 1)) / Q points.