Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-130 | 27th September 2006 00:00

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

RSS-Feed




TR06-130
Authors: Tanmoy Chakraborty, Samir Datta
Publication: 11th October 2006 15:35
Downloads: 2921
Keywords: 


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 NC^2, and
Limaye et. al. improved the bound to $\LogCFL$. Barrington
et. al. showed that evaluating monotone upward stratified
circuits, 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.



ISSN 1433-8092 | Imprint