Theory and Applications of Information-Based Complexity

点击翻译按钮获取中文摘要

This project addresses three areas of research in information- based complexity:Theory, Applications, Software. THEORY: A major theme is the study of the computational complexity of multivariate problems in a large number of variables. In particular, the computational complexity of path integrals, that is, integrals in an infinite number of variables, will be studied. Often high dimensional multivariate problems are intractable in the worst case deterministic setting. The research emphasis will be on conditions which yield tractability and strong tractability in various settings. A second research area is to explain why low-discrepancy sequences are excellent for computing the high dimensional integrals (often, the dimensionality is in the hundreds) of mathematical finance. This belief is based on extensive software testing but there is no satisfactory theoretical explanation. The goal is to characterize very high dimensional integrals for which low-discrepancy sequences are superior to Monte Carlo. A third area is to continue research on the computational complexity of implementation testing for continuous problems. APPLICATIONS: The theory will be applied to a number of application areas, including computational complexity and new algorithms for combinatorial circuit verification. SOFTWARE: The FINDER software library contains modifications of low-discrepancy sequences. FINDER has been made available to researchers in various disciplines. Further improvements, tests, and dissemination of FINDER are planned.