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.