Skip to main content

On the Complexity of Matrix Powering, Sum of Square Roots, and Related Problems

Joël Ouaknine ( University of Oxford )

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...

Share this: