Complexity as a new challenge for mathematicians

Abstract

We discuss the computational complexity of three problems: matrix multiplication, multivariate integration of smooth periodic function, and multivariate approximation of smooth functions. The first two problems are studied in the worst case setting whereas the third problem is studied in the average case setting with the folded Wiener sheet measure. These three problems serve as an illustration that computational complexity presents a new set of questions whose answers probably require new proof techniques. That is why even problems which were thoroughly studied in mathematics need to be revisited when we want to find sharp bounds on their complexity.