Theory of Computing
-------------------
Title : Polynomial Identity Testing via Evaluation of Rational Functions
Authors : Ivan Hu, Dieter van Melkebeek, and Andrew Morgan
Volume : 20
Number : 1
Pages : 1-70
URL : https://theoryofcomputing.org/articles/v020a001
Abstract
--------
We introduce a hitting set generator for Polynomial Identity Testing
based on evaluations of low-degree univariate rational functions at
abscissas associated with the variables. We establish an equivalence
up to rescaling with a generator introduced by Shpilka and Volkovich,
which has a similar structure but uses multivariate polynomials.
We initiate a systematic analytic study of the power of hitting set
generators by characterizing their vanishing ideals, i.e., the sets of
polynomials that they fail to hit. We provide two such
characterizations for our generator. First, we develop a small
collection of polynomials that jointly produce the vanishing ideal. As
corollaries, we obtain tight bounds on the minimum degree, sparseness,
and partition class size of set-multilinearity in the vanishing ideal.
Second, inspired by a connection to alternating algebra, we develop a
structured deterministic membership test for the multilinear part of
the vanishing ideal. We present a derivation based on alternating
algebra along with the required background, as well as one in terms of
zero substitutions and partial derivatives, avoiding the need for
alternating algebra. As evidence of the utility of our analytic
approach, we rederive known derandomization results based on the
generator by Shpilka and Volkovich and present a new application in
derandomization / lower bounds for read-once oblivious algebraic
branching programs.
------------------------
A conference version of this paper appeared in the Proceedings of the
13th Innovations in Theoretical Computer Science Conference.