Semi-algebraic complexity and models for massive data set processing

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

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.