Computational Complexity Lower Bounds

本研究项目考察了各种设置下的计算复杂性。特别是，本研究的重点是获得在这些领域中解决特定问题的复杂性的下界。主要目标是扩展过去十年中开发的电路复杂性，通信复杂性和资源权衡下界的技术主体，并找到这些技术证明下界的新应用。一些特定的兴趣领域是图连通性的研究，在下界中使用多方通信复杂性，分支程序的力量，以及将电路复杂性技术扩展到命题逻辑中证明复杂性的领域-这是我们理解NP和co-NP之间关系的基础主题。

This research project examines computational complexity in a variety of settings. In particular, this research focuses on obtaining lower bounds on the complexity of solving specific problems in these domains. The main goal is to extend the body of techniques in circuit complexity, communication complexity, and resource tradeoff lower bounds that have been developed over the last decade and find new applications of these techniques for proving lower bounds. Some specific areas of interest are the study of graph connectivity, the use of multi-party communication complexity in lower bounds, the power of branching programs, and the extension of circuit complexity techniques into the domain of the complexity of proofs in propositional logic --- a subject that is fundamental to our understanding of the relationship between NP and co-NP.