Header menu link for other important links
X
A note on parameterized polynomial identity testing using hitting set generators
Purnata Ghosal,
Published in Elsevier B.V.
2019
Volume: 151
   
Abstract
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. © 2019 Elsevier B.V.
About the journal
JournalData powered by TypesetInformation Processing Letters
PublisherData powered by TypesetElsevier B.V.
ISSN00200190
Open AccessNo
Concepts (11)
  •  related image
    Computer applications
  •  related image
    Data processing
  •  related image
    Arithmetic circuit
  •  related image
    HITTING SET GENERATORS
  •  related image
    PARAMETERIZED COMPLEXITY
  •  related image
    Partial derivatives
  •  related image
    Polynomial identity testing
  •  related image
    RANDOM PARTITIONS
  •  related image
    SUM OF PRODUCTS
  •  related image
    Theory of computation
  •  related image
    Polynomials