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.