Lower Bounds and Structural Results in Complexity Theory

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

Three major issues are addressed in this project: 1) the computational power of Boolean circuits with threshold gates, as well as their ability to "learn" (with an emphasis on the development of techniques for proving lower bounds); 2) the mathematical structure of complexity classes and degrees in low-level complexity theory; and 3) the relationship between combinatorial and extensional properties of a set and its computational complexity.