Semi-algebraic complexity and models for massive data set processing

海量数据集处理的半代数复杂性和模型

• 批准号: 0830626
• 负责人: Paul Beame
• 金额: $ 41.45万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830626&HistoricalAwards=false
• 关键词: Semi; algebraic; complexity; models; massive

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.

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. 它们被广泛用于操作研究和组合优化。 该项目的一部分是要调查使用半代数推断可以有效地得出的内容，包括基于半代数推断的不可满足性证明的复杂性，线性和半决赛编程的质量和NP-HARD优化问题，可以使用已知的半galgebraic comperive tor lareverive afferiage comperive Inferive tor Leverive我们的理解，并将其理解为范围。对实际数字的半代数推断类别的算法。网络计算机允许积累前所未有的大小的数据集。 仅给出近似答案，可以有效地处理此类大规模数据集的新分布式方法在实践中产生重大影响。 但是，迄今已分析的大规模数据集处理的理论模型仅代表了非常有限的方法，并且不捕获已经在实践中使用的技术。 这项研究的一部分旨在生产和分析理论模型，使我们能够了解这些方法的局限性大规模数据集处理并更好地利用它们。多方属性沟通复杂性测量必须在多个参与者之间传达的信息量，每种信息都必须在功能上提供部分信息，以计算其输入，以计算其输出。 由于其灵活性，它广泛适用于计算复杂性问题。 该项目的最终目标是将可用于分析多方通信复杂性的相当有限的技术添加，其目的是将其应用于半代数推断和分布式大规模数据集处理。