On Matrix Powering and Related Problems

I will discuss the Matrix Powering Positivity Problem, PosMatPow : given an m × m square integer matrix M , a linear function f : Z m × m → Z with integer coefficients, and a positive integer n (encoded in binary), determine whether f ( M n ) ≥ 0. Using techniques from algebraic and analytic number theory, it turns out that for fixed dimension m at most 3, one can show that this problem is decidable in polynomial time (the complexity is open in higher dimensions). I will also present and discuss a number of related problems, including the Euclidean Travelling Salesman Problem, the Sum-of-Square-Roots Problem, and the Positivity Problem for Straight-Line Programs ( PosSLP ). This is joint work with James Worrell and Esther Galby.