Communication Complexity, Proof Complexity, and Approximation
Communication Complexity, Proof Complexity, and Approximation
批准号:
0514870
负责人:
Paul Beame
金额:
$20.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2005
资助国家:
美国
项目状态:
已结题
起止时间:
2005-06-01 至 2009-05-31
中文摘要
本提案包含计算复杂性一般领域内的三个主要研究课题。他们考虑了(1)通信复杂性:计算无界实体在分布式环境中计算并非所有实体可用的输入的共享函数所需的信息量的度量,以及(2)证明复杂性:表示命题逻辑重言式(和不满意的公式)的证明的复杂性作为这些重言式大小的函数。近似在这两个领域的研究中都起着重要作用。在解决计算问题时,时间和空间之间的权衡是计算复杂性的基础。在许多情况下,可以通过使用更多的时间来重新计算中间结果而不是存储它们来节省空间。此外,时间和空间之间的关系是计算复杂性的主要开放问题之一。其中最重要的一点是,是否所有可有效解决的问题都可以使用小空间来解决。计算复杂性是分析时空权衡的最佳方法的关键,但是需要更强大的计算复杂性模型来分析更细粒度级别的计算。海量数据集已经无处不在,其增长速度比随机存取存储器还要快。为了有效地处理这些庞大的数据集,算法必须利用数据通常可以更快地顺序传输的事实。此外,就像在互联网环境中一样,数据可能会消失。这些特征导致了流算法的研究,这些算法基于对无序数据的单次扫描来计算数据集的属性。为了使这些算法的空间要求小而可行,产生的答案必须是近似值。通信复杂度分析一直是研究流算法的主要工具,但现有的关于近似问题的研究成果非常有限。根据Cook定理,证明在输入公式的大小上是多项式有界的证明系统的存在性等价于NP = coNP。虽然这种理解是证明复杂性的最终目标,但证明复杂性在推理系统的设计中也有许多应用,这些应用在实践中很有用,对于理解np困难问题的复杂性也很重要。本文的研究内容包括以下三个方面:(1)研究通信复杂性的新模型,以获得更强的时空权衡下界为目标。(2)系统研究通信复杂性中的近似问题,目标是利用流(及相关)算法为更广泛的问题获得边界。(3)对证明复杂性的研究,包括在分析近似算法中使用证明复杂性,与通信复杂性的联系,可满足实例(包括随机实例)的搜索算法,以及更强大的推理算法。提出的证明复杂性研究与可满足性搜索和一般自动推理的算法直接相关,这些任务是人工智能和形式验证的主要工具。统计物理学和人工智能领域的研究人员提出,随机问题中相变的性质与其相关的计算复杂性之间存在很强的联系。PI和其他人最近对证明复杂性的研究揭示了这些领域之间的联系。PI与统计物理和人工智能领域的研究人员有着互动记录。拟议的研究将继续致力于弥合统计物理学、组合学和理论计算机科学方法之间的差距,并将鼓励思想的交流。通信复杂性是如此重要,以至于它必然影响到计算机科学中广泛的主题。已知技术的影响列表已经涵盖了从形式化验证中使用的obdd的特性到VLSI布局的效率到数据库系统中的流算法等应用。提出的关于近似问题的通信复杂性的研究将产生一系列应用于流算法的结果,并将允许将这些概念扩展到图形管道。
英文摘要
This proposal encompasses three main subjects of research within the general field of computational complexity. They consider (1) communication complexity: the measure of the amount of information required by computationally unbounded entities in a distributed environment to compute shared functions of inputs that are not available to all entities, and (2) proof complexity: the complexity of expressing proofs of propositional logic tautologies (and unsatisfiable formulas) as a function of the size of these tautologies. Approximation plays a role in the research in both of these areas.Intellectual Merits Tradeoffs between the time and space used to solve computational problems are fundamental in computational complexity. In many instances one can save space by employing more time to recompute intermediate results rather than storing them. Moreover, the relationship between time and space is one of the major open questions in computational complexity. One of the most important is whether or not every efficiently-solvable problem can be solved using small space. Computational complexity is the key to the best methods of analysis for time-space tradeoffs but more powerful models of computational complexity are required to analyze comptutation at a finer-grained level. Massive data sets have become ubiquitous and are growing faster than random access memories. To handle these massive data sets efficiently, algorithms must use the fact that data can typically be transferred more quickly sequentially. Moreover, as in the internet context, the data can be evanescent. These features have led to the study of streaming algorithms which compute properties of datasets based on a single sweep through the unordered data. To keep the space requirements of these algorithms small and feasible, the answers produced are necessarily approximations. Analysis of communication complexity has been the major tool for studying streaming algorithms but existing results on approximation problems are very limited. By Cook's theorem, the existence of proof systems whose proofs are polynomially-bounded in the sizes of the input formulas is equivalent to NP = coNP. Although such an understanding is the ultimate goal of proof complexity, proof complexity also has many applications in the design of inference systems that are useful in practice and important for understanding the complexity of NP-hard problems.Research Topics The proposed research encompasses all three of these areas: (1) research on new models of communication complexity with the goal of obtaining stronger time-space tradeoff lower bounds. (2) research on a systematic study of approximation problems in communication complexity with the goal of obtaining bounds for a wider variety of problems using streaming (and related) algorithms. (3) research onproof complexity including the use of proof complexity in analyzing approximation algorithms, connections to communication complexity, search algorithms on satisfiable instances (including random instances), and more powerful inferencing algorithms.Broader Impact The proposed research on proof complexity has direct relevance to algorithms for satisfiability search and general automated inference, tasks which are major tools in AI and formal verification. Researchers in statistical physics and AI have suggested a strong connection between the properties of phase transitions in random problems and their associated computational complexity. Recent research on proof complexity by the PI and others has shed light on the connections between these areas. The PI has a record of interactions with researchers in statistical physics and AI. The proposed research will continue work on briding the gap between the methodologies of statistical physics, combinatorics and theoretical computer science and will encourage the cross-fertilization of ideas. Communication complexity is so fundamental that it necessarily impacts a broad range of topics within computer science. The list of impacts of the known techniques already encompasses applications ranging from properties of OBDDs used in formal verification to the efficiency of VLSI layout to streaming algorithms in database systems. The proposed research on the communication complexity of approximation problems will yield a body of results for application to streaming algorithms and will permit the extension of these notions to graphics pipelines as well.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Complexity of Representations for Inference
-
批准号:2006359
-
项目类别:Standard Grant
-
资助金额:$35.0万
-
财政年份:2020
-
负责人:Paul Beame
-
依托单位:
SHF: Small: Efficient Verification of Nonlinear Arithmetic
-
批准号:1714593
-
项目类别:Standard Grant
-
资助金额:$45.0万
-
财政年份:2017
-
负责人:Paul Beame
-
依托单位:
AF: Small: Communication and Resource Tradeoffs
-
批准号:1524246
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2015
-
负责人:Paul Beame
-
依托单位:
AF: Small:Tradeoffs among Measures in Computational and Proof Complexity
-
批准号:1217099
-
项目类别:Standard Grant
-
资助金额:$44.0万
-
财政年份:2012
-
负责人:Paul Beame
-
依托单位:
AF: Large: Collaborative Research: Reliable Quantum Communication and Computation in the Presence of Noise
-
批准号:1111382
-
项目类别:Continuing Grant
-
资助金额:$128.63万
-
财政年份:2011
-
负责人:Paul Beame
-
依托单位:
Travel Support for IEEE Symposium on Foundations of Computer Science (FOCS 2011)
-
批准号:1147364
-
项目类别:Standard Grant
-
资助金额:$1.2万
-
财政年份:2011
-
负责人:Paul Beame
-
依托单位:
Travel Support for the Symposium on Foundations of Computer Science (FOCS 2010)
-
批准号:1049485
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2010
-
负责人:Paul Beame
-
依托单位:
AF: Small: Graph Isomorphism and Quantum Random Walks by Anyons
-
批准号:0916400
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2009
-
负责人:Paul Beame
-
依托单位:
Semi-algebraic complexity and models for massive data set processing
-
批准号:0830626
-
项目类别:Continuing Grant
-
资助金额:$41.45万
-
财政年份:2008
-
负责人:Paul Beame
-
依托单位:
ITR: Inference in AI, Verification, and Theory: A Unified Approach
-
批准号:0219468
-
项目类别:Continuing Grant
-
资助金额:$49.0万
-
财政年份:2002
-
负责人:Paul Beame
-
依托单位:
Lower Bounds for Time-space Tradeoffs, Data Structures, and Proof Complexity
-
批准号:0098066
-
项目类别:Standard Grant
-
资助金额:$29.7万
-
财政年份:2001
-
负责人:Paul Beame
-
依托单位:
Computational and Proof Complexity Bounds
-
批准号:9800124
-
项目类别:Standard Grant
-
资助金额:$21.3万
-
财政年份:1998
-
负责人:Paul Beame
-
依托单位:
Computational Complexity Lower Bounds
-
批准号:9303017
-
项目类别:Continuing Grant
-
资助金额:$19.32万
-
财政年份:1994
-
负责人:Paul Beame
-
依托单位:
PYI: Resource Bounds and Parallel Computation.
-
批准号:8858799
-
项目类别:Continuing Grant
-
资助金额:$27.45万
-
财政年份:1988
-
负责人:Paul Beame
-
依托单位:
海外基金