Efficient Algorithms for Multivariate Problems

许多重要的问题涉及到具有大量变量d的函数。有时d是以百、千为单位，甚至是无界的，就像路径积分中的情况一样。经典的算法是不适合这样的问题，因为他们的成本增加指数快速与d。此外，在函数类的经典假设下，所有算法都是昂贵的，因为相应的多变量问题是棘手的。这就是为什么需要设计新的假设和新的方法，以保证有效的算法的存在与弱得多的依赖于d。一个重要的部分，所提出的研究将集中在确定重要的易处理的问题，并得出相应的有效算法。特别是，在这个方向上的一个重大进展，预计有小的有效尺寸的问题。由于一些重要问题的最坏情况下的棘手性，可以避免切换到其他设置，有效的算法也将在平均情况下和随机设置进行研究。本文对再生核Hilbert空间上定义的问题给出了肯定的结果，理论工作将为许多迄今为止只能在少量变量下求解的重要问题提供新的有效算法。这些算法将被开发和彻底测试。研究成果和软件将通过各种电子期刊、期刊出版物、会议介绍和一个专门网页迅速传播。虽然不支持这项补助金，研究生将参与研究和算法开发。

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.