Computational Complexity Theory and Circuit Complexity

This research will study the complexity of computation using the framework of Boolean circuit complexity. Special emphasis is placed on the following topics: Strong separations of circuit classes: If known separations of small circuit complexity classes could be strengthened, it would imply separations on larger time- and space-complexity classes. This connection will be investigated, using the notion of "immunity" as a tool. Width-bounded reducibility: This notion will be used as a tool to investigate the relationships among "similar" complexity classes. This project also investigates threshold circuits, an structure of the complexity class P/poly.