Computational Complexity Theory and Circuit Complexity

The goal of research in complexity theory is to classify the complexity of real world computational problems by providing lower bounds on the resources required to solve them. To date - in spite of impressive lower bounds for restricted types of circuits- almost the only useful progress toward this goal has come via the tool of reducibility, which allows one to show that problem is complete for complexity class.

Many of the most important complexity classes can be characterized in terms of Boolean circuits of restricted size or depth, etc. Recently, it has become apparent that arithmetic circuits are also very useful in this regard. The relationships between Boolean and arithmetic circuit complexity are still only poorly understood, although there has been significant progress on this front recently. This project will work to clarify these relationships further.

Specially, this project will exploit new insights about the complexity of arithmetic operation, in order to investigate the power of small space-bounded complexity classes and complexity classes defined in terms of small-depth circuits. Also the tools of Kolmogorov complexity will be applied, in order to obtain a better understanding of the complexity of graph reachability problems. More generally, the project will attempt to clarify the relationship among complexity classes, and the various notions (nondeterminism, unambiguity, symmetry, Boolean and arithmetic circuits, etc.) that define models of computation characterizing important complexity classes.