Evaluating monotone circuits on cylinders, planes, and tori

We re-examine the complexity of evaluating monotone planar circuits MPCVP, with special attention to circuits with cylindrical embeddings. MPCVP is known to be in NC 3, and for the special case of upward stratified circuits, it is known to be in LogDCFL. We characterize cylindricality, which is stronger than planarity but strictly generalizes upward planarity, and make the characterization partially constructive. We use this construction, and four key reduction lemmas, to obtain several improvements. We show that stratified cylindrical monotone circuits can be evaluated in LogDCFL, arbitrary cylindrical monotone circuits can be evaluated in AC 1 (LogDCFL), while monotone circuits with one-input-face planar embeddings can be evaluated in LogCFL. For monotone circuits with focused embeddings, we show an upper bound of AC 1 (LogDCFL). We re-examine the NC 3 algorithm for general MPCVP, and note that it is in AC 1 (LogCFL) = SAC 2. Finally, we show that monotone circuits with toroidal embeddings can, given such an embedding, be evaluated in NC. Also, special kinds of arbitrary genus circuits can also be evaluated in NC