Title: The computational complexity of modular forms

Speaker: Charles Denis, Microsoft Research

Abstract: The Fourier coefficients of modular forms encode important arithmetic information. In this talk we consider the problem of computing these Fourier coefficients. We show that this problem is quite hard in general. For instance, there are modular forms whose Fourier coefficients are #P-hard to compute. We also show that computing the Fourier coefficients of a Hecke eigenform is at least as hard as factoring integers. On the algorithmic side we will give a brief description of the methods used to compute these Fourier coefficients.