Randomness in Computation and Proof

本研究旨在加深我们对复杂性理论中随机性与计算之间相互作用的理解。调查集中在交互式证明系统，概率可检查证明，组合优化问题的近似性等方面，以及相关领域。其中一个目标是研究几种方法，在这些方法中，可以改进概率可检验证明的构造，从而加强推导出的近似性的下界。此外，还计划对这些结构可能提出的有用结构进行研究，例如具有新特性的纠错码。其他目标是研究概率结构之间的可约性，并考虑存在对这些结构具有普适性的对象的可能性。

This research aims to further our understanding of the interplay between randomness and computation in complexity theory. The investigation concentrates on aspects of interactive proof systems, probabilistically checkable proofs, the approximability of problems in combinatorial optimization, and related areas. One goal is to examine several ways in which construction of probabilistically checkable proofs may be improved and in so doing strengthen the derived lower bounds on approximability. In addition, a study is planned of useful structures that may be suggested by these constructions, such as error-correcting codes with novel properties. Other goals are to investigate reducibility among probabilistic constructions and to consider the possibility that there are objects that are universal for such constructions.