How to exclude noise from a polynomial

Question

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?

Answer 1

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$?

Answer 2

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