Average Case and Probabilistic Setting of Information-Based Complexity

只有部分或污染信息的问题 出现在许多学科：计算机科学，物理和化学， 控制理论，统计，预测和估计，科学和 工程计算、物理学、决策理论和金融。 而且这 获取信息往往很昂贵。 信息化的目标 复杂性是创建一个计算复杂性理论， 部分，污染和定价信息，并应用 解决不同学科的具体问题。 的主要焦点 该项目包括： (1)打破顽固：许多问题 在科学、工程甚至金融领域， 一个很大的变量数d。 然而，典型的多变量问题是 在最坏的情况下确定性设置难以处理。 唯一能打破 棘手是通过切换到另一种设置来削弱保证。 随机化、平均病例和概率设置将继续研究。 在 特别是，它已被证明是多元整合和 平均而言，这两种近似都是非常容易处理的。 证明是非构造性的;如何在d维中采样以实现强 正在处理易处理性问题。 (2)软件开发和测试：理论 研究已经产生了用于重要问题的算法， 维度整合 为了使这些方法得到广泛应用， 开发和测试。 由于这些方法包含大量的固有的 并行性，实现是在工作站网络上完成的。 还计划在并行计算机上进行测试。 现实世界的问题用于 试验. (3)分段光滑函数的概率复杂度： 分段光滑函数出现在不同的科学和技术领域 例如计算机视觉、图像和信号处理、科学计算 气象学、地震学和测绘学。 由于负面的结果， 最坏的情况下，这些问题正在研究中， 概率设置 积分、近似和检测的新算法 奇异点正在研究和实施。

Problems with only partial or contaminated information arise in many disciplines: computer science, physics and chemistry, control theory, statistics, prediction and estimation, scientific and engineering computation, geophysics, decision theory, and finance. Furthermore, this information is often expensive to obtain. The goal of information-based complexity is to create a computational complexity theory for problems with partial, contaminated, and priced information, and to apply the results to solving specific problems in varied disciplines. The prime foci of this project are the following: (1) Breaking Intractability: Many problems in science, engineering, and even finance, deal with functions that have a large number, d, of variables. However, typical multivariate problems are intractable in the worst case deterministic setting. The only way to break intractability is to weaken the assurance by switching to another setting. Randomized, average case, and probabilistic settings continue to be studied. In particular, it has been proven that multivariate integration and approximation are both strongly tractable on the average. The proof is non- constructive; the problem of how to sample in d dimensions to achieve strong tractability is being addressed. (2) Software Development and Testing: Theoretical investigations have led to algorithms for important problems such as high dimensional integration. To make these methods widely available, software is being developed and tested. Since these methods contain a large amount of inherent parallelism, the implementation is being done on a workstation network. Testing is also planned on parallel computers. Real-world problems are used for testing. (3) Probabilistic Complexity of Piece-Wise Smooth Functions: Piece-wise smooth functions arise in diverse areas of science and technology such as computer vision, image and signal processing, scientific computation, meteorology, seismology, and to mography. Because of negative results of the worst-case setting these problems are being studied in the probabilistic setting. New algorithms for integration, approximation, and detection of singular points are being studied and implemented.