Algebraic dependence testing in the perspective of algebraic matroids

Computational Complexity;Algebraic Complexity;Arithmetic Circuits;Algebraic Matroids;Algebraic Dependence;Annihilating Polynomials;Linear Representation

Liu, Minghao ; Forbes ; Michael A

关键词: Computational Complexity;    Algebraic Complexity;    Arithmetic Circuits;    Algebraic Matroids;    Algebraic Dependence;    Annihilating Polynomials;    Linear Representation;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/108061/LIU-THESIS-2020.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

We study the computational problem called algebraic dependence testing, where we seek to find a polynomial relation among a set of polynomials. This notion generalizes linear dependence, and understanding it has had applications to deterministic polynomial identity testing and algebraic circuit lower bounds. We present previous works on this topic including Perron's bound on the annihilating polynomial and the Jacobian criterion. By Perron's bound, there is a brute-force algorithm that solves for the annihilating polynomial in exponential time. By the Jacobian criterion, infields with large or zero characteristics, we can represent the polynomials with a set of vectors while preserving independence, thus reducing the problem to linear dependence testing. We present the above results and discuss their discrepancy in complexity. While algebraic independence gives rise to a class of matroids, this relation is rarely discussed in the computer science literature. We then describe the previous results on algebraic dependence testing in the perspective of algebraic matroids, and hope to provide powerful tools and novel directions to explore on this topic in future.