No label defined (Q4250165)

Let \(F\) be a finite field and let \(f:F^k \to F\) be a polynomial of degree \(\leq d\). One is given \(n\) equalities of the form \[ f(x)=y, \qquad (x,y) \in F^k \times F, \] of which only some unspecified \(t\) equalities are known to be correct. Based on this information, one has to find a small number of possible candidates for \(f\). It is assumed that the \(t\) corresponding sampling points \(x\) are random, uniformly distributed on \(F^k\), and independent, and that the probability of failure must be small. Let \(L=[\root {k+1} \of {(k+1)! dn}]\). For \(t \geq {1 \over k!}({k+1 \over 2}+L)^k\) and \(| F| \gg tL\), the author gives an algorithm that solves the above problem in time poly(\(n\)). A more general scheme, involving an adversary that is allowed to decide which \(t\) equalities should be considered correct, is also discussed. For the entire collection see [Zbl 0904.00049].