Consider the Parvaresh-Vardy list decoder.

As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of these field elements (interpreted as univariate polynomials over a base field) on all the elements of the base field. This was so that on interpolating to get a multivariate polynomial $Q(x,y_1,y_2,\dots)$, we have a root fining step comprising simply solving for the points lying on $Q=0$ and the curve.

An important consideration here was that $Q$ (the curve) not be identically zero as a polynomial, or that the curve not lie on the hypersurface defined by $Q=0$. This is ensured by taking $Q$ of smallest degree and not divisible by $E$, and by taking the exponent h to be large enough. Basically we adjust degrees of $Q$ and the curve to ensure that the curve does not lie on the surface.

My question is this: Is there any significance to the choice of the Parvaresh Vardy curve as defined, beyond this degree requirement to ensure the curve isn't contained in the hyperplane? For instance, could we choose the curve to be simpler, say of the form $(f,f^2 mod E, f^3 mod E,\dots)$? In this case, lets say we take $Q$ to be linear in the $y_i$'s (as used in linear-algebraic list-decoding of folded codes, say) so that the function applied on the curve , $Q(f,f^2,f^3,f^4,\dots)$, cannot be identically zero.

Everywhere it is mentioned that the tuple of functions is "carefully chosen" to ensure the method goes through, but I am unable to see what exactly is the motivation for this particular choice of curve. This method is also used in the expander construction of Guruswami-Umans-Vadhan. Also, in a subsequent paper by Ta-Shma-Umans, another curve is used, but that curve too is similar to the Parvaresh-Vardy curve, but using linear combinations of the functions used in the former.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.