It is necessary to activate JavaScript to navigate this site.

Grant P202/10/0854     1.1.2010 - 31.12.2012
Grantor: Czech Science Foundation (GAČR)

Circuit complexity and self-reducibility

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:

Koucký Michal

 IM team members:  
Polach František
 Participating institutions:

Institute of Mathematics, AS CR