Communication Complexity, Proof Complexity, and Approximation

这一建议包括在计算复杂性的一般领域内的三个主要研究主题。他们考虑(1)通信复杂性：计算无界实体在分布式环境中计算输入的共享函数所需的信息量，而不是所有实体都可用；(2)证明复杂性：将命题逻辑重言式(和不可满足公式)的证明表示为这些重言式大小的函数的复杂性。近似在这两个领域的研究中都扮演着重要的角色。解决计算问题所用的时间和空间之间的智力优势权衡是计算复杂性的基础。在许多情况下，人们可以通过使用更多的时间来重新计算中间结果而不是存储它们来节省空间。此外，时间和空间之间的关系也是计算复杂性方面的主要开放问题之一。最重要的问题之一是，是否每个有效可解的问题都可以用很小的空间来解决。计算复杂性是最好的时空权衡分析方法的关键，但需要更强大的计算复杂性模型才能在更细粒度的级别上分析计算。海量数据集已经变得无处不在，而且增长速度比随机存取存储器更快。为了有效地处理这些海量数据集，算法必须利用这样一个事实，即数据通常可以更快地按顺序传输。此外，就像在互联网环境中一样，数据可能是瞬息万变的。这些特征导致了流算法的研究，该算法基于对无序数据的一次扫描来计算数据集的属性。为了保持这些算法对空间的要求小且可行，所产生的答案必然是近似的。通信复杂性分析一直是流媒体算法研究的主要工具，但现有的关于近似问题的结果非常有限。根据Cook定理，证明在输入公式的大小上多项式有界的证明系统的存在性等价于NP=coNP。虽然这样的理解是证明复杂性的最终目标，但证明复杂性在推理系统的设计中也有许多应用，这些应用在实践中是有用的，对于理解NP-Hard问题的复杂性也很重要。研究主题本研究包括以下三个方面：(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.