Files in this item



application/pdfLIU-THESIS-2020.pdf (431kB)
(no description provided)PDF


Title:Algebraic dependence testing in the perspective of algebraic matroids
Author(s):Liu, Minghao
Advisor(s):Forbes, Michael A
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computational Complexity
Algebraic Complexity
Arithmetic Circuits
Algebraic Matroids
Algebraic Dependence
Annihilating Polynomials
Linear Representation
Abstract: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.
Issue Date:2020-05-14
Rights Information:Copyright 2020 Minghao Liu
Date Available in IDEALS:2020-08-26
Date Deposited:2020-05

This item appears in the following Collection(s)

Item Statistics