Personal tools
You are here: Home Events Abstract Archives 2003 Circuits on Cylinders

Circuits on Cylinders

Peter Bro Miltersen 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.

Document Actions