{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108061"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108061","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algebraic dependence testing in the perspective of algebraic matroids","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Liu, Minghao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Forbes, Michael A"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T21:58:08Z","date_published":"2020-08-26T21:58:08Z","updated_at":"2026-07-22T22:24:47Z","subjects":["Computational Complexity","Algebraic Complexity","Arithmetic Circuits","Algebraic Matroids","Algebraic Dependence","Annihilating Polynomials","Linear Representation"],"languages":["en"],"rights":["Copyright 2020 Minghao Liu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108061","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Forbes, Michael A"]},{"key":"dc:creator","label":"Author","values":["Liu, Minghao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T21:58:08Z","2020-05-14","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Complexity","Algebraic Complexity","Arithmetic Circuits","Algebraic Matroids","Algebraic Dependence","Annihilating Polynomials","Linear Representation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Minghao Liu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108061"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Minghao Liu, accepted the attached license on 2020-05-13 at 23:36.","The student, Minghao Liu, submitted this Thesis for approval on 2020-05-13 at 23:52.","This Thesis was approved for publication on 2020-05-14 at 09:08.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15388 on 2020-08-25 at 17:14:42","Made available in DSpace on 2020-08-26T21:58:08Z (GMT). No. of bitstreams: 9 LIU-THESIS-2020.pdf: 430601 bytes, checksum: 607672005dae273752e36a49de7dbb39 (MD5) IEEE_ECE.bst: 59476 bytes, checksum: 7668c5e97bcc2d22a9f8d4eab9b269ee (MD5) algdep.tex: 45041 bytes, checksum: 74d71752d6f4ba133b31ab8777b2734d (MD5) csthesis.tex: 5368 bytes, checksum: a45f3f66a9f09ed96228e32343977cdf (MD5) intro.tex: 5996 bytes, checksum: ce9e240b821862fbeb1021b3e808f534 (MD5) matroid.tex: 21016 bytes, checksum: b42aec2df93550d491a2bca8f6e87ee0 (MD5) thesisrefs.tex: 276 bytes, checksum: 7bcd82e47c5771a2ab9707e0f21fea75 (MD5) uiuc_csthesis18.cls: 20136 bytes, checksum: 9dfa8da06157a2b2cf73403294c8a8d5 (MD5) LICENSE.txt: 4208 bytes, checksum: 4958c1d5c5e0405e384bb1ddf599bd4c (MD5) Previous issue date: 2020-05-14"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algebraic dependence testing in the perspective of algebraic matroids"]}]}],"canonical_facts":{"dc:contributor":["Forbes, Michael A"],"dc:creator":["Liu, Minghao"],"dc:date":["2020-08-26T21:58:08Z","2020-05-14","2020-05"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Minghao Liu, accepted the attached license on 2020-05-13 at 23:36.","The student, Minghao Liu, submitted this Thesis for approval on 2020-05-13 at 23:52.","This Thesis was approved for publication on 2020-05-14 at 09:08.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15388 on 2020-08-25 at 17:14:42","Made available in DSpace on 2020-08-26T21:58:08Z (GMT). No. of bitstreams: 9 LIU-THESIS-2020.pdf: 430601 bytes, checksum: 607672005dae273752e36a49de7dbb39 (MD5) IEEE_ECE.bst: 59476 bytes, checksum: 7668c5e97bcc2d22a9f8d4eab9b269ee (MD5) algdep.tex: 45041 bytes, checksum: 74d71752d6f4ba133b31ab8777b2734d (MD5) csthesis.tex: 5368 bytes, checksum: a45f3f66a9f09ed96228e32343977cdf (MD5) intro.tex: 5996 bytes, checksum: ce9e240b821862fbeb1021b3e808f534 (MD5) matroid.tex: 21016 bytes, checksum: b42aec2df93550d491a2bca8f6e87ee0 (MD5) thesisrefs.tex: 276 bytes, checksum: 7bcd82e47c5771a2ab9707e0f21fea75 (MD5) uiuc_csthesis18.cls: 20136 bytes, checksum: 9dfa8da06157a2b2cf73403294c8a8d5 (MD5) LICENSE.txt: 4208 bytes, checksum: 4958c1d5c5e0405e384bb1ddf599bd4c (MD5) Previous issue date: 2020-05-14"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108061"],"dc:language":["en"],"dc:rights":["Copyright 2020 Minghao Liu"],"dc:subject":["Computational Complexity","Algebraic Complexity","Arithmetic Circuits","Algebraic Matroids","Algebraic Dependence","Annihilating Polynomials","Linear Representation"],"dc:title":["Algebraic dependence testing in the perspective of algebraic matroids"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:47Z"}