Computational Complexity Lower Bounds

点击翻译按钮获取中文摘要

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.