Grant P202/10/0854
1.1.2010 - 31.12.2012
Grantor: Grant Agency of Czech Republic (GACR)
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.
Participating institutions:
Institute of Mathematics AS CR
People:
EN
