Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
复制标题
DOI：
10.1145/3519935.3520025
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Robert Andrews;Michael A. Forbes
中科院分区：
文献类型：
--
作者：
Robert Andrews;Michael A. Forbes
我们证明了由n×n矩阵X的r×r个子式生成的理想中的任何非零多项式都可以有效地逼近行列式。具体地说，对于这一理想中的任意非零多项式f，我们构造了一个在边界复杂性意义上逼近Θ(r1/3)×Θ(r1/3)行列式的小的深度三预言回路。对于许多类代数电路，这意味着由r×r子式生成的理想中的每个非零多项式至少与Θ(r1/3)×Θ(r1/3)行列式一样难近似计算。我们还证明了2n×2n次对称矩阵的Pfaffian和2r×2r主子矩阵的Pfaffian生成的理想的类似结果。这回答了Grochow最近提出的关于边界复杂性设置中多项式理想的复杂性的问题。利用多项式理想的复杂性和代数复杂性中的其他问题之间的联系，我们的结果提供了一个通用配方，允许行列式的下界应用于代数复杂性中的其他问题。我们给出了几个这样的应用程序，其中两个在下面突出显示。我们证明了Grochow和Pitassi的理想证明系统的新下界。具体地说，我们给出了由低深度回路计算的反驳的超多项式下界。这扩展了Limaye等人最近突破的低深度电路下限。关于证明复杂性的设定。此外，对于许多自然电路类，我们的硬实例的近似证明复杂性由行列式的近似电路复杂性决定。我们还构造了用于低深度回路闭合的新的碰集生成器。对于任意ε>；0，我们构造了种子长度为O(nε)的生成器，它命中n元低深度回路。我们的生成器在种子长度和阶数之间达到了近乎最佳的折衷，并且可以通过近线性大小的低深度电路进行计算(相对于其输出的大小)。这与Limaye等人最近获得的发电机的种子长度相匹配，但改进了发电机的程度和电路复杂性。
We show that any nonzero polynomial in the ideal generated by the r × r minors of an n × n matrix X can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial f in this ideal, we construct a small depth-three f-oracle circuit that approximates the Θ(r1/3) × Θ(r1/3) determinant in the sense of border complexity. For many classes of algebraic circuits, this implies that every nonzero polynomial in the ideal generated by r × r minors is at least as hard to approximately compute as the Θ(r1/3) × Θ(r1/3) determinant. We also prove an analogous result for the Pfaffian of a 2n × 2n skew-symmetric matrix and the ideal generated by Pfaffians of 2r × 2r principal submatrices. This answers a recent question of Grochow about complexity in polynomial ideals in the setting of border complexity. Leveraging connections between the complexity of polynomial ideals and other questions in algebraic complexity, our results provide a generic recipe that allows lower bounds for the determinant to be applied to other problems in algebraic complexity. We give several such applications, two of which are highlighted below. We prove new lower bounds for the Ideal Proof System of Grochow and Pitassi. Specifically, we give super-polynomial lower bounds for refutations computed by low-depth circuits. This extends the recent breakthrough low-depth circuit lower bounds of Limaye et al. to the setting of proof complexity. Moreover, we show that for many natural circuit classes, the approximative proof complexity of our hard instance is governed by the approximative circuit complexity of the determinant. We also construct new hitting set generators for the closure of low-depth circuits. For any ε > 0, we construct generators with seed length O(nε) that hit n-variate low-depth circuits. Our generators attain a near-optimal tradeoff between their seed length and degree, and are computable by low-depth circuits of near-linear size (with respect to the size of their output). This matches the seed length of the generators recently obtained by Limaye et al., but improves on the degree and circuit complexity of the generator.