2
$\begingroup$

Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields.

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you make the question self-contained? In particular, what are $E,f,Q$, how do you define the curve? $\endgroup$
    – Felipe Voloch
    Jun 21, 2015 at 14:38
  • $\begingroup$ @FelipeVoloch: Sorry for not including the info. I had to start somewhere, and didn't want to make it too long. E is an irreducible polynomial of degree n over $\mathbb{F}_q$, f is a polynomial of degree at most n-1. Like in Reed-Solomon coding, we evaluate f and in this case also the functions f^h mod E, etc. at points of the field. Q is a multivariate polynomial used to interpolate and list-decode $\endgroup$
    – BharatRam
    Jun 21, 2015 at 15:26
  • $\begingroup$ the code. Parvaresh-Vardy code is thus a bundle of Reed-Solomon type codes which allow for elegant list-decoding. The idea is to to interpolate using the entries of the corrupted codeword to get Q and then solve for points with Q=0 and lying on the curve $(f,f^h mod E,\dots)$. This is a very conensed explanation, but if you want more, I'll edit the question details and add a primer. $\endgroup$
    – BharatRam
    Jun 21, 2015 at 15:29
  • 1
    $\begingroup$ Bharat, I don't think I can help you. I'm just a little bit curious. About 10 years ago I attended a talk where Alex Vardy outlined a variant of RS-codes, where they were able to develop a Sudan style list decoding algorithm that could do something close to soft decision decoding (may be there were some assumptions about the types of soft errors the algorithm could accomodate?). Is this the same construction? $\endgroup$
    – Jyrki Lahtonen
    Jul 14, 2015 at 21:29

0

Reset to default

Your Answer

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