Consider a polynomial $P\in{\mathbb F}[X]$ where ${\mathbb F}$ is a finite field and $P$ is of degree $f$.

Given the set of points $(1,y_1),\ldots,(n,y_n)$ where $n=3f+1$ and $f$ is the upper bound on the number of noisy points, that is, let $M\subset[n]$ such that $|M|\leq f$ we know that for all $i\in[n]\smallsetminus M$ it follows that $P(i)=y_i$ whereas for $i\in M$ we have $P(i)\neq P(i)$.

It is known that we can decode $P$ from $(1,y_1),\ldots,(n,y_n)$ in this case, so these points are correctable encoding of $P$.

However, when the degree of $P$ is $2f$ it is impossible to decode $P$ from $(1,y_1),\ldots,(n,y_n)$ with $f$ noisy points.

My question is, if I get another new point $(x^\star, y^\star)$ which is known to be correct (i.e. $P(x^\star)=y^\star$), can I do something better? Can I detect even a single faulty point? Can I even pick up 2 points such that one of them is faulty? - that would be helpful as well.

If I cannot do anything - is there other encoding that allows me to do so when I obtain a known correct point?

  • 1
    $\begingroup$ How do you view $1,2,\ldots,n$ as elements of $\Bbb{F}$? Shouldn't they really be $x_1,x_2,\ldots,x_n$ instead? Or is the characteristic of $\Bbb{F}$ larger than $n$? $\endgroup$ – Jyrki Lahtonen Aug 9 '18 at 17:57
  • $\begingroup$ You are right, either take ${\mathbb F}$ be a prime field or consider $i$ as $x_i\in{\mathbb F}$ $\endgroup$ – Bush Aug 9 '18 at 17:59
  • 1
    $\begingroup$ But, degree $2f$ sounds way too high. Degree close to $f$ you could probably do something with Sudan's list decoding algorithm. I'm afraid I don't remember the list decoding bounds to say something more precise. $\endgroup$ – Jyrki Lahtonen Aug 9 '18 at 18:03
  • $\begingroup$ A point is that if you could reliably detect enough faulty points then you could turn this errors-only-decoding problem into an errors-and-erasures-decoding problem. Reed-Solomon codes being MDS I don't think that can be reliably done, feels like some known facts would then be violated. I need to think more. $\endgroup$ – Jyrki Lahtonen Aug 9 '18 at 18:14
  • $\begingroup$ @JyrkiLahtonen thanks for your time. Note that detecting even one faulty point would be enough for me. Or even a weaker requirement of picking 2 points such that it is guaranteed that one of them is faulty. $\endgroup$ – Bush Aug 9 '18 at 18:24

If you are given that $P(x^\star)=y^\star$, then this tells you that $P(x)=Q(x)(x-x^\star)+y^\star$ for some polynomial $Q$ of degree $f-1$. Therefore, this transforms the problem as follows: $$ \begin{array}{lcl} \text{Find }P(x) & \implies & \text{Find }Q(x) \\ \text{deg }P=f & \implies & \text{deg }Q=f-1 \\ P(i)=y_i \text{ for at least $n-m$ values of }i & \implies & Q(i)=\frac{y_i-y^\star}{i-x^\star} \text{ for at least $n-m$ values of }i \\ \end{array} $$ In other words, you have the exactly same problem, with different $y_i$ values, except that the degree has decreased. Therefore, your question becomes

If you are given $\deg Q=2f-1$, and at most $f$ points of $\{(i,y_i)\mid 1\le i \le 3f+1\}$ are noisy, then is it possible to

  • recover $Q$?
  • find a $j$ for which $Q(j)\neq y_j$?
  • find $j\neq k$ so either $Q(j)\neq y_j$ or $Q(k)\neq y_k$?
  • $\begingroup$ Nice, thank you. The new question has an answer? It looks easier than the previous one, but still I don't know if there is an efficient way to exclude noisy points. $\endgroup$ – Bush Aug 9 '18 at 17:49
  • $\begingroup$ @Bush Unfortunately, this is not exactly my wheelhouse... $\endgroup$ – Mike Earnest Aug 9 '18 at 17:54

Very nice question.

There has been a lot of recent work (which I am only broadly familiar with) on list decoding of Reed Solomon and related codes, by various researchers, including Guruswami, Rudra, Parvaresh, Vardy. For careful choice of some parameters of RS and so-called folded RS codes, they can give explicit decoding algorithms. Perhaps your question can be cast in this form, though it would probably take some work.

For example, Venkat Guruswami gave a nice overview talk on these topics at the European Info Theory Summer School. There are some explicit decoding algorithms in that talk as well, multivariate interpolation plays a part. A quick read indicates that (summary on slide no. 32) these recent improvements enable one to correct a fraction of up to $\tau$ errors where $$\tau\geq 1-R-\varepsilon,$$ with $R$ the code rate.

However this comes at the cost of alphabet size $$ q \sim N^{\Omega({1/\varepsilon^2})}, $$ where $N$ is the blocklength. By comparison, the original Guruswami-Sudan list decoding algorithms from almost 20 years ago, decoded a fraction of up to $$\tau \sim 1-\sqrt{R}$$ errors [worse since $\sqrt{R}>R$ for $R\in (0,1)$]. Their alphabet size was essentially equal to the blocklength

  • $\begingroup$ Thank you for your time! I will look into it. $\endgroup$ – Bush Aug 16 '18 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.