Efficient Algorithms for Multivariate Problems

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

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.