scientific article; zbMATH DE number 1303541
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].
- Reconstructing multivariate trigonometric polynomials by sampling along generated sets
- Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces
- Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices
- Reconstructing distributions of multivariate random functions under orthogonal polynomial projection approximation
- Sampling of homogeneous polynomials and approximating multivariate functions
- A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions
- Reconstruction of numerical derivatives from scattered noisy data
- Reconstruction of Multidimensional Signals From Irregular Noisy Samples
- Random Sampling of Multivariate Trigonometric Polynomials
- scientific article; zbMATH DE number 2020198
- Multiaffine polynomials over a finite field
- Noisy interpolation of sparse polynomials in finite fields
- Pole recovery from noisy data on imaginary axis
- Learning polynomials with queries: The highly noisy case
- Polynomial representations of the Diffie-Hellman mapping
- Reconstructing curves in three (and higher) dimensional space from noisy data
- Making polynomials robust to noise
- Fitting algebraic curves to noisy data
- Polynomial whitening for high-dimensional data
- Practical cryptanalysis of pseudorandom correlation generators based on quasi-abelian syndrome decoding
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4250165)
