Revision #1 Authors: Ivan Hu, Dieter van Melkebeek, Andrew Morgan

Accepted on: 22nd February 2024 10:51

Downloads: 18

Keywords:

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.

TR22-115 Authors: Dieter van Melkebeek, Andrew Morgan

Publication: 17th August 2022 17:04

Downloads: 466

Keywords:

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.