标题： 代数伪随机性在$VNC^0$ 显示英文标题

标题： Algebraic Pseudorandomness in $VNC^0$

摘要： 我们研究了击中集生成器的算术复杂性，这些伪随机对象用于多项式恒等式测试问题的去随机化。 我们给出了新的显式击中集生成器构造，其输出可以在$VNC^0$中计算，即可以通过常数大小的算术公式计算。 无条件地，我们构造了一个$VNC^0$-可计算的生成器，可以击中常数深度和多项式大小的算术电路。 我们还给出了在强但合理的硬度假设下的条件构造，得到了$VNC^0$-可计算的生成器，分别可以击中多项式大小的算术公式和算术分支程序。 作为我们构造的推论，我们得出了 Grochow 和 Pitassi 的几何理想证明系统子系统的下界。 此类生成器的构造在 Kayal 关于消零多项式的次数下界的研究中是隐含的。 我们的主要贡献是一个其正确性依赖于电路复杂性下界而非次数下界的构造。 显示英文摘要

摘要： We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in $VNC^0$, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a $VNC^0$-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of $VNC^0$-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.