Noisy interpolation of sparse polynomials in finite fields
This paper gives a polynomial time algorithm for the sparse noisy interpolation problem: recover an unknown polynomial of weight at most \(w\): \[ f(x)=\sum_{j=1}^w a_jx^{e_j}\in \mathbb F_p[x], \] with the \(e_j\) known, from approximate values of \(f(t)\) at polynomially many points \(t\in\mathbb F_p\) selected uniformly at random. The case \(f(x)=ax\) is the hidden number problem introduced by Boneh and Venkatesan. The proposed algorithm extends a previous one of the first author, valid in small degrees, to cover polynomials of large (but bounded) degree. The new approach was motivated by by Waring's problem.
- Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
- Interpolation and approximation of polynomials in finite fields over a short interval from noisy values
- The complexity of sparse polynomial interpolation over finite fields
- Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
- scientific article; zbMATH DE number 871950
- Sparse polynomial interpolation over fields with large or zero characteristic
- Sparse interpolation over finite fields via low-order roots of unity
- Sparse polynomial approximation in finite fields
- Noisy interpolating sets for low-degree polynomials
- Noisy polynomial interpolation and noisy Chinese remaindering
- A hidden number problem in small subgroups
- BOUNDS ON EXPONENTIAL SUMS AND THE POLYNOMIAL WARING PROBLEM MOD p
- Computational Complexity of Sparse Rational Interpolation
- Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes
- scientific article; zbMATH DE number 1643920 (Why is no real title available?)
- scientific article; zbMATH DE number 1303541 (Why is no real title available?)
- scientific article; zbMATH DE number 481965 (Why is no real title available?)
- scientific article; zbMATH DE number 2079409 (Why is no real title available?)
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- scientific article; zbMATH DE number 1775429 (Why is no real title available?)
- scientific article; zbMATH DE number 6469260 (Why is no real title available?)
- scientific article; zbMATH DE number 6472645 (Why is no real title available?)
- scientific article; zbMATH DE number 967590 (Why is no real title available?)
- scientific article; zbMATH DE number 3091928 (Why is no real title available?)
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- List decoding of algebraic-geometric codes
- Noisy polynomial interpolation and noisy Chinese remaindering
- On the hardness of approximating the permanent of structured matrices
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Public Key Cryptography – PKC 2004
- Randomness efficient identity testing of multivariate polynomials
- Reconstructing Algebraic Functions from Mixed Data
- Sparse polynomial approximation in finite fields
- The complexity of sparse polynomial interpolation over finite fields
- Polynomial interpolation and identity testing from high powers over finite fields
- Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- Noisy polynomial interpolation modulo prime powers
- Noisy polynomial interpolation and noisy Chinese remaindering
- Study and improvement of the multiplicative noisy polynomial interpolation algorithm on integral ring
- Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
- Correcting noisy exponentiation black-boxes modulo a prime
- Sparse polynomial approximation in finite fields
- Interpolation and approximation of polynomials in finite fields over a short interval from noisy values
- A hidden number problem in small subgroups
This page was built for publication: Noisy interpolation of sparse polynomials in finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2491980)
