Third Symposium on Complexity of Approximately Solved Problems

这个奖项是为了部分支持一个关于近似解决问题的研讨会。问题被近似地解决，要么是因为我们不能准确地解决它们，要么是因为我们选择不去解决它们。在物理科学、工程、人工智能、经济学等领域，由于信息（数据）是局部的、被污染的，我们无法准确解决很多问题。然而，有时候，我们自己的选择是满足于近似，因为它要便宜得多。这个研讨会是由两个概念的交集来定义的：复杂性和近似解。近似可解问题的复杂性理论是研究解决问题的内在困难的下界，并寻求获得最优信息和最优算法的理论。它在最坏情况、平均情况和概率设置下研究这些问题。研讨会包括理论和应用两个方面。

This award is for partial support of a symposium on approximately solved problems. Problems are solved approximately either because we cannot solve them exactly ir because we choose not to. There are many problems in physical science, engineering, artificial intelligence, and economics that we cannot solve exactly because the information (data) is partial and contaminated. Sometimes, however, it is our own choice to settle for approximation because it is significantly cheaper. The symposium is defined by the intersection of two ideas: complexity and approximate solution. A complexity theory for approximately solved problems is one that studies lower bounds on the intrinsic difficulty of solving a problem and seeks to obtain optimal information and optimal algorithms. It studies these questions in worst case, average case, and probabilistic settings. The symposium includes both theory and applications.