The project proposes to study two areas of computational complexity: circuits of bounded depth and self-reducibility of functions. In the area of circuits of bounded depth we aim to study the class of functions computed by small-polynomial size circuits, the relationship between depth and size of circuits, and equivalence of circuit classes. In the area of self-reducibility we intend to study downward self-reducibility and instance compression. The main goal of the project is to bring further understanding of classes of functions computed by small depth circuits and their relationship to larger complexity classes.
Main investigator:
IM team members:
|
Polach František |
Mapa | Autor | Webmaster
