论文标题
多项式身份测试通过评估有理功能
Polynomial Identity Testing via Evaluation of Rational Functions
论文作者
论文摘要
$ \ newCommand {\ ie} {i。\，e。} $我们基于与变量相关的腹部腹部相关的低度单变量合理函数的评估，为多项式身份测试引入了击球集。我们建立了与Shpilka和Volkovich引入的发电机进行重新缩放的等效性，该发电机具有相似的结构，但使用了多元多项式。 我们通过表征其消失的理想，即未能击中的多项式集合来启动对击中集合发电机的力量的系统分析研究。我们为发电机提供两个这样的特征。首先，我们开发了一小部分多项式，共同产生了消失的理想。作为推论，我们在消失的理想中以最小程度，稀疏度和分区类别的大小获得了紧密的界限。其次，受到与交替代数的连接的启发，我们为消失的理想的多线性部分开发了结构化确定性构件测试。我们提出了基于交替代数以及所需的背景的推导，以及零取代和部分衍生物的派生，避免了对交替代数的需求。 作为我们分析方法实用性的证据，我们基于Shpilka和Volkovich的发电机进行重新验证的已知降低结果，并在derandomization / Lower Bounds中提出了一个新的应用程序，以读取读取式的代数分支程序。
$ \newcommand{\ie}{i.\,e.} $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, \ie, 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.
