University of Illinois Urbana-Champaign

Algebraic dependence testing in the perspective of algebraic matroids

Liu, Minghao

Permalink

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

Description

Title
Algebraic dependence testing in the perspective of algebraic matroids
Author(s)
Liu, Minghao
Issue Date
2020-05-14
Director of Research (if dissertation) or Advisor (if thesis)
Forbes, Michael A
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(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.
Graduation Semester
2020-05
Type of Resource
Thesis
Permalink
http://hdl.handle.net/2142/108061
Copyright and License Information
Copyright 2020 Minghao Liu

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science