Efficient Algorithms for Multivariate Problems

许多重要的问题都涉及到具有大量变量的函数。有时候d是百位的，千位的，甚至无界的就像在路径积分中一样。经典算法对于这类问题是不够的，因为它们的代价随着d呈指数级增长。而且，在经典的函数类假设下，所有的算法都是非常昂贵的，因为对应的多元问题是难以处理的。这就是为什么需要设计新的假设和新的方法来保证对d依赖性较弱的有效算法的存在。提议的研究的重要部分将集中在识别重要的可处理问题并推导相应的有效算法上。特别是对于有效维数较小的问题，这一方向有望取得重大进展。由于一些重要问题的最坏情况的棘手性可以通过切换到其他设置来避免，因此我们还将研究在平均情况和随机设置下的有效算法。对于定义在再现核希尔伯特空间上的问题，期望得到积极的结果。理论工作将产生新的和有效的算法来解决到目前为止只能解决少数变量的许多重要问题。这些算法将被开发和彻底测试。研究成果和软件将通过各种电子摘要、期刊出版物、会议报告和一个特别的网页迅速传播。虽然不支持该基金，研究生将参与研究和算法开发。

A number of important problems deal with functions that have a large number d of variables. Sometimes d is in hundreds, thousands, or even unbounded as it is the case in path integration. The classical algorithms are inadequate for such problems since their costs increase exponentially fast with d. Moreover, under the classical assumptions on the classes of functions, all algorithms are prohibitively expensive since the corresponding multivariate problems are intractable. This is why new assumptions and new approaches need to be devised to guarantee an existence of efficient algorithms with much weaker dependence on d.A significant part of the proposed research will concentrate on identifying important tractable problems and deriving the corresponding efficient algorithms. In particular, a significant progress in this direction is expected for problems that have small effective dimension. Since the worst case intractability of some important problems can be avoided by switching to other settings, efficient algorithms will be studied also in the average case and randomized settings. Positive results are expected here for problems defined over reproducing kernel Hilbert spaces.Theoretical work will yield new and efficient algorithms for a host of important problems that so far could only be solved for small number of variables. These algorithms will be developed and thoroughly tested. Research results and software will be promptly disseminated using various electronic digests, journal publications, conference presentations, and a special web page. Although not supported by this Grant, graduate students will be involved in the research and algorithm development.