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.
