Semi-algebraic complexity and models for massive data set processing

本项目专注于半代数推理和海量数据集处理中问题的计算复杂性，以及推进多方通信复杂性的分析技术，这是理解这两个领域问题的有用工具。半代数推理系统利用多项式不等式表示约束集，并利用推理规则从已有的多项式不等式推导出新的多项式不等式。它们被广泛应用于运筹学和组合优化中。这个项目的一部分是研究使用半代数推理可以有效地推导出什么，包括基于半代数推理的不可满足性证明的复杂性，可以使用已知的半代数推理推导出的NP-hard优化问题的线性和半定规划近似的质量，我们对二元域推理的理解可以在多大程度上被用来为实数上的半代数推理类产生更好的算法。联网的计算机使空前规模的数据集得以积累。新的分布式方法通过只给出近似的答案来有效地处理如此庞大的数据集，在实践中产生了重大影响。然而，迄今为止所分析的大量数据集处理的理论模型只代表了非常有限的一类方法，并且没有捕获已经在实践中使用的技术。这项研究的一部分旨在产生和分析理论模型，使我们能够理解这些方法在处理大量数据集时的局限性，并更好地利用它们。多方通信复杂性衡量多个参与者之间必须通信的信息量，每个参与者都有关于函数输入的部分信息，以便计算其输出。由于其灵活性，它被广泛应用于计算复杂性的问题。这个项目的最终目标是增加一组相当有限的技术，可以用来分析多方通信的复杂性，目的是提高其应用到半代数推理和分布式海量数据集处理。

This project focuses on the computational complexity of problems in semi-algebraic inference and in massive data set processing, as well as on advancing the analytical techniques of multiparty communication complexity, which has been a useful tool for understanding problems in both of these areas.Semi-algebraic inference systems express sets of constraints using polynomial inequalities and use rules of inference to derive new polynomial inequalities from existing ones. They are widely used in operations research and combinatorial optimization. Part of this project is to investigate what can be derived efficiently using semi-algebraic inference, including the complexity of proofs of unsatisfiability based on semi-algebraic inference, the quality of the linear and semi-definite programming approximations for NP-hard optimization problems that can derived using known semi-algebraic inference, and the extent to which our understanding of inference over binary domains can be leveraged to yield better algorithms for classes of semi-algebraic inference over the real numbers.Networked computers have allowed the accumulation of data sets of unprecedented size. New distributed methods that process such massive data sets efficiently by giving only approximate answers are having substantial impact in practice. However, the theoretical models of massive data set processing that have been analyzed to date represent only a very limited class of methods and do not capture techniques already used in practice. Part of this research is aimed at producing and analyzing theoretical models that will allow us to understand the limitations of these methods for massive data set processing and to make better use of them.Multiparty communication complexity measures the amount of information that must be communicated between multiple participants, each having partial information about the inputs to a function, in order to compute its output. Because of its flexibility it is widely applicable to problems in computational complexity. The final goal of this project is to add to the rather limited set of techniques that can be used to analyze multiparty communication complexity with the aim goal of improving its applications to semi-algebraic inference and distributed massive data set processing.