On the Complexity of Matrix Powering, Sum of Square Roots, and Related Problems
We examine problems from elementary arithmetic and geometry
whose obvious solutions require exponential time and space, and discuss
instances in which such problems might solvable with better complexity
(especially polynomial time). More of a survey than a hard technical talk,
includes work in progress and plenty of open questions...