Algebraic dependence testing in the perspective of algebraic matroids

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, in fields 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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Liu, Minghao

Contributors dc:contributor

• Forbes, Michael A

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

Statement dc:rights

• Copyright 2020 Minghao Liu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/108061

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/108061