David Mix Barrington: Monotone Planar Circuits
The problem of evaluating a boolean circuit is complete for the class P. The
problem remains complete if we restrict ourselves to planar circuits (that
can be drawn without crossing wires) or monotone circuits (that have no NOT
gates). But there are efficient parallel algorithms (in the class NC) to
evaluate circuits that are both monotone and planar. I will survey some of
these results, including my paper with Lu, Miltersen, and Skyum in CCC'99
and a recent paper of Limaye, Mahajan, and Sarma.