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.