Algorithms and Complexity for some Multivariate Problems

2019/05/03 by David Krieg, Krieg, David
Computer Science · Mathematics · #41A25 #41A46 #41A55 #41A63 #41A65 #52A23 #60B20 #65C05 #65D15 #65D30 #65J99 #65K10 #65Y20 #Complexity and Algorithms in Graphs #FOS: Mathematics #Machine Learning and Algorithms #Mathematical Approximation and Integration #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1905.01166

openalex publication_date 2019/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We study multivariate problems like function approximation, numerical integration, global optimization and dispersion. We obtain new results on the information complexity n(ε,d) of these problems. The information complexity is the amount of information (e.g. the number of function values) that is needed to solve the d-dimensional problem up to a prescribed error ε>0. We present optimal algorithms for some of these problems. An extended abstract can be found in the section "Introduction and Results".

Related

• A brief history of information-based complexity
• Several Approaches to Break the Curse of Dimensionality
• Average case complexity of linear multivariate problems
• Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
• On Optimal Recovery and Information Complexity in Numerical Differentiation and Summation