Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-115 | 22nd February 2024 10:51

Polynomial Identity Testing via Evaluation of Rational Functions

RSS-Feed




Revision #1
Authors: Ivan Hu, Dieter van Melkebeek, Andrew Morgan
Accepted on: 22nd February 2024 10:51
Downloads: 18
Keywords: 


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. 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.



Changes to previous version:

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.


Paper:

TR22-115 | 17th August 2022 17:02

Polynomial Identity Testing via Evaluation of Rational Functions


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. 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