DOI: 10.1145/3637529.3637532 ISSN: 1932-2240

An Approximation Algorithm for the Nearest Decomposable Polynomial in the Hamming Distance

Hiroshi Sekigawa
  • Microbiology (medical)
  • Immunology
  • Immunology and Allergy

A univariate polynomial f is decomposable if it is the composition f = g ( h ) of polynomials g and h whose degrees are at least two. We consider the nearest decomposable polynomial to a given polynomial f in the Hamming distance. We propose a polynomial-time approximation algorithm for the nearest decomposable polynomial and analyze the quality of the output.

More from our Archive