Polynomial Identity Testing via Evaluation of Rational Functions
Polynomial Identity Testing via Evaluation of Rational Functions
复制标题
DOI：
10.4230/lipics.itcs.2022.119
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
D. Melkebeek;Andrew Morgan
中科院分区：
文献类型：
--
作者：
D. Melkebeek;Andrew Morgan
我们引入了一个击中集生成器多项式身份测试的基础上评估的低程度的一元有理函数在与变量相关的dupissas。我们建立了一个等价的重新缩放与发电机介绍了Shpilka和Rumovich，它有一个类似的结构，但使用多元多项式。我们开始了一个系统的分析研究的权力击中集发电机的特点，他们消失的理想，即，它们不能命中的多项式集合。我们为我们的生成器提供了两个这样的特征。首先，我们开发了一个小集合的多项式，共同产生消失的理想。作为推论，我们得到的最小程度，稀疏性和分区类大小的集合多重线性消失的理想上的紧界。第二，启发连接到交替代数，我们开发了一个结构化的确定性成员资格测试的多线性部分消失的理想。我们提出了一个推导的基础上交替代数沿着与所需的背景，以及一个在零替换和偏导数，避免了交替代数的需要。作为我们的分析方法的效用的证据，我们重新推导已知的去随机化结果的基础上的发电机Shpilka和Alzheovich，并提出了一个新的应用程序在去随机化/下界读一次不经意的代数分支程序。
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.