Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-115 | 17th August 2022 17:02

Polynomial Identity Testing via Evaluation of Rational Functions



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.

ISSN 1433-8092 | Imprint