Get all the updates for this publication

Conferences

Testing polynomial equivalence by scaling matricesPublished in Springer Verlag

2017

Volume: 10472 LNCS

Pages: 111 - 122

In this paper we study the polynomial equivalence problem: test if two given polynomials f and g are equivalent under a non-singular linear transformation of variables. We begin by showing that the more general problem of testing whether f can be obtained from g by an arbitrary (not necessarily invertible) linear transformation of the variables is equivalent to the existential theory over the reals. This strengthens an NP-hardness result by Kayal [9]. Two n-variate polynomials f and g are said to be equivalent up to scaling if there are scalars a1, …, an F\{0} ∈such that f(a1, …, an) = g(x1, …, xn). Testing whether two polynomials are equivalent by scaling matrices is a special case of the polynomial equivalence problem and is harder than the polynomial identity testing problem. As our main result, we obtain a randomized polynomial time algorithm for testing if two polynomials are equivalent up to a scaling of variables with black-box access to polynomials f and g over the real numbers. An essential ingredient to our algorithm is a randomized polynomial time algorithm that given a polynomial as a black box obtains coefficients and degree vectors of a maximal set of monomials whose degree vectors are linearly independent. This algorithm might be of independent interest. It also works over finite fields, provided their size is large enough to perform polynomial interpolation. © Springer-Verlag GmbH Germany 2017.

Topics: Matrix equivalence (70)%70% related to the paper, Matrix polynomial (70)%70% related to the paper, Stable polynomial (68)%68% related to the paper, Polynomial matrix (66)%66% related to the paper and Alternating polynomial (65)%65% related to the paper

View more info for "Testing Polynomial Equivalence by Scaling Matrices"

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Data powered by TypesetSpringer Verlag |

ISSN | 03029743 |

Open Access | No |

Concepts (17)

- Codes (symbols)
- Computation theory
- Equivalence classes
- Linear transformations
- Mathematical transformations
- Matrix algebra
- Polynomial approximation
- Polynomials
- Finite fields
- LINEARLY INDEPENDENTS
- NP-HARDNESS RESULTS
- POLYNOMIAL EQUIVALENCE
- Polynomial identity testing
- POLYNOMIAL INTERPOLATION
- Polynomial-time algorithms
- TRANSFORMATION OF VARIABLES
- BLACK-BOX TESTING