AF: Small: Noise Across Computational Settings

该项目将扩大我们对噪声的理解，并开发在各种计算环境中应对和受益于噪声的新工具。这个项目考虑的环境可以分为三组：(1)交互通信；(2)电路计算；(3)动态系统，当被视为计算设备时。在这些设置中考虑噪声的影响会产生许多有趣而重要的问题。在理论层面上，该项目的目标是开发新的纠错方案，以便在处理使用不可靠组件的计算时进行纠错，并指出此类方案的局限性。在实践层面上，这项研究可能会导致更有效的纠错通信方案的开发，以及更省电的电路的开发。在技术层面上，这项提议的交叉主题是使用信息论来更好地了解不同环境中噪声的影响。国际和平研究所和其他人在该项目下研究的领域过去的工作表明，在这些不同的环境之间将会有技术转移。该项目连接了几个学科：交互纠错处于传统编码理论和通信复杂性之间的尖端；电路纠错是复杂性理论和计算机体系结构中都感兴趣的；以及研究噪声动态系统的计算方面将理论计算机科学、动力学系统和理论物理结合在一起。该项目的更广泛影响包括课程开发、扩大学生在理论领域的参与以及撰写调查文章。

The project will expand our understanding of noise and develop new tools for coping with, and benefiting from noise in a variety of computational settings. Settings considered under this project can be broken into three groups: (1) interactive communication; (2) circuit computation; and (3) dynamical systems when viewed as computing devices. Considering the effect of noise in each of these settings yields many interesting and important problems. At a theoretical level, the project aims to develop new schemes for error-correction when dealing with computation using unreliable components, as well as to map out the limitations of such schemes. At a practical level, the research may lead to the development of more efficient error-correcting communication schemes, and more power efficient circuits.At a technical level, the cross-cutting theme of this proposal is using information theory to better understand the effect of noise in the different settings. Past work by the PI and others in the areas studied under this project, suggests that there will be a transfer of techniques between these different settings. The project connects several disciplines: interactive error-correction is on the cusp between traditional coding theory and communication complexity; circuit error correction is of interest within both complexity theory and computer architecture; and the study of computational aspects of noisy dynamical systems brings together theoretical computer science, dynamical systems, and theoretical physics. Broader impacts of the project include curriculum development, broaden participation of students in theoretical areas and writing survey articles.