Department of Computer Science
University of Aarhus
4pm Tuesday 4 February 2003
Room 2511, JCMB, King's Buildings
In this talk we consider the computational power of cylindrical circuits. We show that every polynomial size constant depth circuit with at most one layer of MOD gates and at most two layers of AND/OR-gates above the MOD gates can be simulated by a polynomial size constant width cylindrical circuit. On the other hand, we show that every polynomial size constant width cylindrical circuit can be simulated in ACC^0.
This is joint work with Kristoffer Arnsfelt Hansen and V Vinay.