Sparse polynomial approximation in finite fields

DOI10.1145/380752.380803zbMath1323.68321OpenAlexW2020638838MaRDI QIDQ5175970

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

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

Related Items (7)

Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation ⋮ Correcting noisy exponentiation black-boxes modulo a prime ⋮ On the Bit Security of Elliptic Curve Diffie–Hellman ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Noisy polynomial interpolation modulo prime powers ⋮ Noisy Chinese remaindering in the Lee norm ⋮ Unnamed Item

Cites Work

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

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