One-input-face MPCVP is Hard for L, but in

Abstract. A monotone planar circuit (MPC) is a Boolean circuit that can be embedded in a plane, and that has only AND and OR gates. Yang showed that the one-input-face monotone planar circuit value problem (MPCVP) is in NC2, and Limaye et. al. improved the bound to LogCFL. Barrington et. al. showed that evaluating monotone upward stratified cir-cuits, a restricted version of the one-input-face MPCVP, is in LogDCFL. In this paper, we prove that the unrestricted one-input-face MPCVP is also in LogDCFL. We also show this problem to be L-hard under quantifier free projections. Key Words: L, LogDCFL, monotone planar circuits.