Abstract:

The most ancient Euclidean algorithm computes the greatest common divisor $\gcd(x,y)$ of two positive numbers using no more than $C\log(\min(x,y))$ divisions, where $C$ is a constant independent of $x,y$; and the more modern Stein algorithm computes $\gcd(x,y)$ using no more than $C\log(\max(x,y))$ subtractions, divisions by 2 and multiplications by 2. Are these algorithms optimal among all algorithms which have access to the same operations? The main purpose of this talk is to introduce through these concrete problems the subject of Arithmetic Complexity, in which these (and many related) questions are made precise and (sometimes) answered. An exciting aspect of this research area is that it requires and combines methods from several fields ---complexity theory, logic and number theory--- but without needing to get too deeply into any one of them. I will attempt to make clear just what methods and results are relevant, and the listener should leave with (at least) a good understanding of the two classical algorithms mentioned above. [Some of the results in the talk are joint with Lou van den Dries.]