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.

Streamlining of the formal proof of the membership test to align better with the outline.

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. Despite the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas.

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 a proof of concept 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.

Full development of the alternating algebra representation in the last section, some reorganization and streamlining of other parts, addition of background on Groebner basis and references to follow-up work.

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. Despite the univariate
nature, we establish an equivalence up to rescaling with a generator
introduced by Shpilka and Volkovich, which has a similar structure but
uses multivariate polynomials in the abscissas.

We study the power of the generator by characterizing its vanishing
ideal, i.e., the set of polynomials that it fails to hit. Capitalizing
on the univariate nature, 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. Inspired by an
alternating algebra representation, we develop a structured
deterministic membership test for the vanishing ideal. As a proof of
concept, we rederive known derandomization results based on the
generator by Shpilka and Volkovich and present a new application for
read-once oblivious algebraic branching programs.