A note on parameterized polynomial identity testing using hitting set generators

摘要

We show that polynomial hitting set generator defined by Shpilka and Volkovich [1] has the following property:If an n-variate polynomial f has a partition of variables such that the partial derivative matrix [2] has large rank then its image under the Shpilka-Volkovich generator too has large rank of the partial derivative matrix even under a random partition.Further, we observe that our main result is applicable to a larger class of hitting set generators that are defined by polynomials that can be represented as a small sum of products of univariate polynomials. (C) 2019 Elsevier B.V. All rights reserved.