Information-Based Complexity of Multivariate Problems

许多涉及实际利益的多元问题在最坏的情况下是难以解决的。可以通过识别允许有效算法的新属性（即类）或切换到平均（或概率）设置来消除这种难处。这通常被称为打破棘手性。拟议研究的很大一部分将涉及打破一些重要问题的棘手性。这将使我们对多元问题的复杂性有更深入的了解，并为许多重要问题提供新的高效算法。与一般案例研究相关的是路径积分。该研究将是最近开始的路径集成复杂性研究的延续，并将提供额外的复杂性界限和新的有效算法。许多重要的问题涉及无界域的函数类。然而，相应的复杂性结果很少，而且在实践中，常用的算法是临时的，不是最优的。提出的研究的重要部分将处理为具有无界域的函数类定义的问题；将研究最坏情况和平均情况的设置。这将丰富对此类问题复杂性的理解，并将提供最优（或几乎最优）的新算法。这项理论工作将为许多重要问题提供新的、有效的算法。这些算法将被开发和彻底测试。研究生将参与研究的理论和发展阶段。

Many multivariate problems of practical interests are intractable in the worst case setting. Such intractability could be removed by either identifying new properties (i.e., classes) that allow for efficient algorithms or by switching to the average (or probabilistic) settings. This is often referred to as breaking intractability. A substantial part of the proposed research will deal with breaking intractability of a number of important problems. This will lead to deeper knowledge of the complexities of multivariate problems and will result in new efficient algorithms for a host of important problems. Related to the average case study are path integrals. The research will be a continuation of a recently initiated study on the complexity of path integration and will provide additional complexity bounds and new efficient algorithms. A number of important problems deal with classes of functions of unbounded domains. However, there are but few corresponding complexity results and, in practice, commonly used algorithms are ad hoc and are not optimal. Significant part of the proposed research will deal with problems defined for classes of functions with unbounded domains; both the worst case and the average case settings will be studied. This will enrich understanding of the complexity of such problems and will provide new algorithms that are optimal (or almost optimal). The theoretical work will yield new and efficient algorithms for a host of important problems. These algorithms will be developed and thoroughly tested. Graduate students will be involved in both theoretical and development phases of the research.