Problem reductions in algorithmic number theory
Eric Bach (University of Wisconsin, USA)
As a field of research, the design and analysis of algorithms for number-theoretic problems draws from two sources. On one hand, there is the pragmatic need, coming from number theory and the areas to which it is applied, to have efficient methods to solve particular problems. On the other hand, there is the theoretical computer scientist's natural desire to classify number-theoretic problems as to their computational difficulty. These two approaches converged in the 1970's, with the advent of provably effective randomized algorithms for problems such as primality. In the decades hence, one recurrent dream has been to build a theory that does for number-theoretic complexity what NP-completeness has done for combinatorial algorithms, and uncover the relations between problems that explain why certain ones are easy and others difficult. This talk will be a report on the status of this project, with some attention paid to recent progess (derandomizations, invading the turf of modular forms, etc.)
Talk slides (PDF).