RUI: Communication Complexity of Distributed Computations

本项目致力于研究通信复杂性，这是分布式计算的一个重要方面，使用H.Abelson的连续模型。它着重于发展一种建立通信复杂性下界结果的一般方法，以及获得一些重要具体问题的下界。为此，进行了一项研究，以了解连续分布式计算的几何结构，并寻求通信复杂性的数学表征。探讨了计算问题的数学结构与其复杂性的关系。还将研究通信复杂性的特征与经典Pfaff问题之间的联系，以及分布式算法设计与Hilbert第13问题之间的联系。对关于下界的几个猜想进行了检验，希望能得出证明或反证的结果。本研究中使用的工具和技术主要来自连续数学的几个分支，如分析、微分几何和拓扑学。为了辅助计算通信复杂性的下界，对数学符号计算软件包进行了扩展和提炼。该程序包对于执行实验以形成和帮助证明关于各种问题的下限的猜想是重要的。这个项目的一个重要部分是为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.