Complexity as a new challenge for mathematicians

  • Henryk Woźniakowski

    Columbia University, New York, United States
Complexity as a new challenge for mathematicians cover
Download Chapter PDF

A subscription is required to access this book chapter.


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.