Information-Based Complexity and Efficient Algorithms for Multivariate Problems

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

ABSTRACT0511994Grzegorz WasilkowskiU of KentuckyThere are many important computational problems dealing with functions of very many (e.g., hundreds or thousands) variables. The classical algorithms work well when the number d of variables is small; however, they fail even for a modest number d since their costs increase exponentially with d. This is why the research will concentrate on tractability of multivariate problems. This will include identifying important problems that are tractable and deriving efficient algorithms for such problems. For problems that are not tractable in the most commonly used worst-case setting, average-case and randomized settings will be used to study their complexity. This will allow to avoid the worst-case intractability by the expense of weaker (random or probabilistic) assurances of the errors. In such cases, efficient randomized algorithms will be proposed, i.e., algorithms that, with a large probability, yield very accurate solutions at small (polynomial in d) cost. Recent observations by a number of researchers indicate that some important problems (e.g., in mathematical finance, physics, statistics, experimental design, etc.) have the so called small effective dimension. This is why a significant effort will be devoted to the complexity study of such problems and to constructions of polynomial-time algorithms. In summary, the research will enhance the understanding of the complexity of multivariate problems and their tractability. It will result in identifying new assumptions/properties that are both relevant to the problems in practice and yield efficient algorithms. Although not supported by this Grant, students will participate in the research.