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.