论文标题
代数硬度与低特征的随机性
Algebraic Hardness versus Randomness in Low Characteristic
论文作者
论文摘要
我们表明，在特征$ p> 0 $的字段上显式恒定变化的多项式的下限足以在特征$ p $的字段上取代多项式身份测试。在这种情况下，对多项式身份测试的硬度随机折衷的现有工作要求特征足够大，或者硬度的概念要比代数复杂性中使用的硬度硬度的标准句法概念更强。我们的结果对该领域的特征没有限制，并使用标准的硬度概念。 我们通过将Kabanets-impagliazzo发电机与白色盒子过程相结合，以采用$ p $ - th的电路根源，计算出特征性$ p $的字段的$ p $ th。当电路中出现的变量数量被一些常数界定时，此过程被证明是有效的，这使我们能够绕过与特征性$ p $中心电路有关的困难。 我们还将Kabanets-Impagliazzo发电机与最近的“自举”结合在一起，从而进行多项式认同测试，以表明一个足够硬的显式恒定变量多项式家族产生了多项式认同测试的几乎完全完整的态度。该结果构成了零和积极特征的领域，并补充了Guo，Kumar，Saptharishi和Solomon的最新作品，他们在特征为零的领域中获得了稍强的陈述。
We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the notion of hardness to be stronger than the standard syntactic notion of hardness used in algebraic complexity. Our results make no restriction on the characteristic of the field and use standard notions of hardness. We do this by combining the Kabanets-Impagliazzo generator with a white-box procedure to take $p$-th roots of circuits computing a $p$-th power over fields of characteristic $p$. When the number of variables appearing in the circuit is bounded by some constant, this procedure turns out to be efficient, which allows us to bypass difficulties related to factoring circuits in characteristic $p$. We also combine the Kabanets-Impagliazzo generator with recent "bootstrapping" results in polynomial identity testing to show that a sufficiently-hard family of explicit constant-variate polynomials yields a near-complete derandomization of polynomial identity testing. This result holds over fields of both zero and positive characteristic and complements a recent work of Guo, Kumar, Saptharishi, and Solomon, who obtained a slightly stronger statement over fields of characteristic zero.
