The path-breaking results of Furst, Saxe, and Sipser and of Ajtai in the early 1980s established that polynomial-sized constant depth circuits AC⁰ cannot compute PARITY. Since then, the small circuit classes AC⁰, ACC⁰, TC⁰, and NC¹ have been the focus of fairly intensive investigation. In 1989, Barrington showed that constant-width circuits, and even branching programs, are equivalent to NC¹. Subsequent work related branching programs over restricted monoids to the other aforementioned circuit classes.

A new thread of investigation, originating in the late 1990s, explored how powerful such branching programs and circuits are in the presence of geometric restrictions. This paper contributes to this latter thread, investigating the effect of imposing cylindricality on constant-width circuits and branching programs. Cylindricality lies between two well-studied restrictions: cylindrical drawings are planar but not necessarily upward planar, and not all planar graphs have cylindrical drawings. This paper shows that cylindrical branching programs can compute more functions than AC⁰; they can simulate circuits computing an AND of ORs of MODs whose inputs are computed in AC⁰. Since all known separations in the small complexity classes essentially hinge around the inability to compute some fixed MOD, cylindrical branching programs cannot be easily separated from higher classes. Nonetheless, they are not too powerful; this paper shows that functions computed by constant-width cylindrical circuits are all computable in ACC⁰. Placing the possibly larger class of constant-width planar circuits also in ACC⁰ was achieved by Hansen by furthering the techniques of this paper.

The proofs of the two main results of the paper are very different in flavor. The lower bound is determined by a direct and intuitive construction. The upper bound involves a reduction to the word problem over a finite monoid M, and a nice but technically involved proof establishing that cylindricality translates to the monoid M being solvable. The paper will be of general interest to complexity theorists, and will appeal highly to those working in circuit complexity.