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.