Mittmann, Johannes: Independence in Algebraic Complexity Theory. - Bonn, 2013. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc:
author = {{Johannes Mittmann}},
title = {Independence in Algebraic Complexity Theory},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2013,
month = dec,

note = {This thesis examines the concepts of linear and algebraic independence in algebraic complexity theory. Arithmetic circuits, computing multivariate polynomials over a field, form the framework of our complexity considerations. We are concerned with polynomial identity testing (PIT), the problem of deciding whether a given arithmetic circuit computes the zero polynomial. There are efficient randomized algorithms known for this problem, but as yet deterministic polynomial-time algorithms could be found only for restricted circuit classes. We are especially interested in blackbox algorithms, which do not inspect the given circuit, but solely evaluate it at some points.
Known approaches to the PIT problem are based on the notions of linear independence and rank of vector subspaces of the polynomial ring. We generalize those methods to algebraic independence and transcendence degree of subalgebras of the polynomial ring. Thereby, we obtain efficient blackbox PIT algorithms for new circuit classes.
The Jacobian criterion constitutes an efficient characterization for algebraic independence of polynomials. However, this criterion is valid only in characteristic zero. We deduce a novel Jacobian-like criterion for algebraic independence of polynomials over finite fields. We apply it to obtain another blackbox PIT algorithm and to improve the complexity of testing the algebraic independence of arithmetic circuits over finite fields.},

url = {}

The following license files are associated with this item: