V Vinay, Indian Institute of Science, Bangalore, India
Department of Computer Science
Teoretisk naturvidenskab
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi2 o MOD o AC0 circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to ACC0.