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.