Sparse polynomial approximation in finite fields

DOI10.1145/380752.380803MaRDI QIDQ5175970zbMATH OpenOpenAlexFDO

Authors Igor E. Shparlinski

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380803

zbMATH Keywords

exponential sumsfinite fieldssparse polynomials

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Cryptography (94A60)

Recommendations

• Noisy interpolation of sparse polynomials in finite fields
• Recovering zeros of polynomials modulo a prime
• Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
• Noisy polynomial interpolation modulo prime powers
• On some approximation problems concerning sparse polynomials over finite fields

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(19)

• Fast construction of constant bound functions for sparse polynomials
• A theory and an algorithm for computing sparse multivariate polynomial remainder sequence
• Noisy Chinese remaindering in the Lee norm
• Noisy polynomial interpolation modulo prime powers
• Binomiality testing and computing sparse polynomials via witness sets
• Noisy interpolation of sparse polynomials in finite fields
• Sparse squares of polynomials
• Recovering zeros of polynomials modulo a prime
• Noisy polynomial interpolation and noisy Chinese remaindering
• The MMO problem
• Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
• Correcting noisy exponentiation black-boxes modulo a prime
• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation
• On the hidden shifted power problem
• Nearly Optimal Sparse Polynomial Multiplication
• scientific article; zbMATH DE number 5038555 (Why is no real title available?)
• On the bit security of elliptic curve Diffie-Hellman
• Complexity of sparse polynomial solving 2: renormalization

This page was built for publication: Sparse polynomial approximation in finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175970)