Information-Based Complexity of Multivariate Problems

点击翻译按钮获取中文摘要

Multivariate problems appear in many diverse applications; yet they are often intractable in the worst case setting. A significant part of the research will concentrate on the study of multivariate problems in the average case setting. In particular, the study of the reduction in complexity by switching from the worst case to the average case setting will be one of the central foci. This will enrich understanding of the average case complexity of important multivariate problems and will provide new algorithms that solve worst case intractable problems with small expected cost and small expected error. Related to the average case analysis are path integrals. The research will provide complexity bounds for his important problem and should reveal new algorithms that are more efficient than Monte Carlo methods (that are commonly used) for some path integrals. One of the approaches in studying path integrals is through the analysis of multivariate weighted integration and approximation over unbounded domains. A part of the research will deal with the complexity of such problems. In addition to theoretical results, the research will result in efficient software for such problems as multivariate integration/approximation, weighted integration/approximation, and path integrals.