Invariant Theory, Tensors and Computational Complexity

The main problem addressed in this dissertation is the problem of giving strong upper bounds on the degree of generators for invariant rings. In the cases of matrix invariants and matrix semi-invariants, we give polynomial upper bounds. An exciting consequence of these bounds is a polynomial time algorithm for rational identity testing. We use an approach inspired by ideas from Popov and Derksen to reduce the problem to finding invariants that define the null cone. The theory of blow-ups of matrix spaces and non-commutative rank is crucial in finding invariants that define the null cone. We also give a polynomial time algorithm for deciding if the orbit closures of two points intersect for matrix invariants and semi-invariants. In addition, we give some applications for proving lower bounds on the border rank of tensors.PHDMathematicsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttps://deepblue.lib.umich.edu/bitstream/2027.42/144049/1/visu_1.pd