RUI: Communication Complexity of Distributed Computations

本项目主要研究分布式计算的一个重要方面--通信复杂性。Abelson 它侧重于发展的一般方法，建立通信复杂性的下限结果，以及获得一些重要的具体问题的下限。 为此，进行了一项研究，以了解连续分布式计算的几何结构，并寻求通信复杂性的数学表征。 探讨了计算问题的数学结构与其复杂性之间的关系。 通信复杂性的表征和经典普法夫的问题之间的连接和分布式算法的设计和希尔伯特的第13个问题也将被调查。 几个关于下界的命题进行了测试，希望得到证明或反证。 本研究中使用的工具和技术主要来自连续数学的几个分支，如分析，微分几何和拓扑学。 为了帮助计算通信复杂度的下限，Mathematica符号计算软件包进行了扩展和改进。 这个软件包对于执行实验以制定和帮助证明关于各种问题的下限的假设是很重要的。 该项目的一个重要组成部分是根据NSF研究本科院校计划，谁是直接参与本研究的各个方面的本科生的夏季研究经验。

This project concentrates on the study of communication complexity, an important aspect of distributed computing, using a continuous model of H. Abelson. It focuses on the development of a general method for establishing lower bound results on communication complexity as well as to obtain lower bounds for some important concrete problems. For that purpose, a study is conducted to understand the geometric structure of continuous distributed computations and to seek a mathematical characterization of communication complexity. Relations of the mathematical structure of the computational problem to its complexity are explored. Connections between the characterization of communication complexity and the classical Pfaff's problem and between the design of distributed algorithms and Hilbert's 13th problem will also be investigated. Several conjectures about lower bounds are tested with the hope that a proof or disproof will result. The tools and techniques used in this study come mainly from several branches of continuous mathematics such as analysis, differential geometry, and topology. To aid the computation of lower bounds on communication complexity, a Mathematica symbolic computing software package is expanded and refined. This package is important for performing experiments in order to formulate and help prove conjectures about the lower bounds for various problems. An important part of this project is the summer research experience for undergraduate students under the NSF Research Undergraduate Institutions Program, who are directly involved in various aspects of this research.