Header menu link for other important links
X
Testing polynomial equivalence by scaling matrices
Published in Springer Verlag
2017
Volume: 10472 LNCS
   
Pages: 111 - 122
Abstract
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.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (17)
  •  related image
    Codes (symbols)
  •  related image
    Computation theory
  •  related image
    Equivalence classes
  •  related image
    Linear transformations
  •  related image
    Mathematical transformations
  •  related image
    Matrix algebra
  •  related image
    Polynomial approximation
  •  related image
    Polynomials
  •  related image
    Finite fields
  •  related image
    LINEARLY INDEPENDENTS
  •  related image
    NP-HARDNESS RESULTS
  •  related image
    POLYNOMIAL EQUIVALENCE
  •  related image
    Polynomial identity testing
  •  related image
    POLYNOMIAL INTERPOLATION
  •  related image
    Polynomial-time algorithms
  •  related image
    TRANSFORMATION OF VARIABLES
  •  related image
    BLACK-BOX TESTING