In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly
many faces. We show that this problem can be solved in LogDCFL thus by a result of Cook, yielding a space-efficient ($O(\log^2{n})$-space) and polynomial time algorithm for the problem. It also yields a highly parallel algorithm (simultaneously $O(\log {n})$-time with polynomially many processors).

This generalises the previous bound of LogDCFL on one input face planar circuits. More precisely, we show that if a monotone circuit is embedded on a surface of genus $g$ and has $k$ faces on which all the inputs are present, then the circuit can be evaluated on a CROW-PRAM (concurrent read \emph{owner} write parallel random access machine)in time $O(g(k+g) \log{n})$ using $n^{O(1)}$ many processors.

Our main technical idea is a distance metric in single sink DAGs that can be computed in deterministic logarithmic space and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We show that the partitioning procedure is in $\Log$. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best bound known is UL $\cap$ coUL and therefore not known to be contained in LogDCFL.

There was a mistake in the statement of the main theorem and its proof which is now fixed along with some other changes. Also updated the abstract.

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly
many faces. We show that this problem can be solved in LogDCFL thus by a result of Cook, yielding a space-efficient ($O(\log^2{n})$-space) and polynomial time algorithm for the problem. It also yields a highly parallel algorithm (simultaneously $O(\log {n})$-time with polynomially many processors).

This generalises the previous bound of LogDCFL on one input face planar circuits. More precisely, we show that if a monotone circuit is embedded on a surface of genus $g$ and has $k$ faces on which all the inputs are present, then the circuit can be evaluated on a CROW-PRAM (concurrent read \emph{owner} write parallel random access machine)in time $O(g(k+g) \log{n})$ using $n^{O(1)}$ many processors.

Our main technical idea is a distance metric in single sink DAGs that can be computed in deterministic logarithmic space and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We show that the partitioning procedure is in $\Log$. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best bound known is UL $\cap$ coUL and therefore not known to be contained in LogDCFL.

There was a mistake in the statement of the main theorem and its proof which is now fixed along with some other changes. Also updated the abstract.

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be solved in LogDCFL thus by a result of Cook, yielding a space-efficient ($O(\log^2{n})$-space) and polynomial time algorithm for the problem. It also yields a highly parallel algorithm (simultaneously $O(\log {n})$-time with polynomially many processors).

This generalises the previous bound of LogDCFL on one input face planar circuits. More precisely, we show that if a monotone circuit is embedded on a surface of genus $g$ and has $k$ faces on which all the inputs are present, then the circuit can be evaluated on a CROW-PRAM (concurrent read \emph{owner} write parallel random access machine) in time $O(g\log (k+g) \log{n})$ using $n^{O(1)}$ many processors.

Our main technical idea is a distance metric in single sink DAGs that can be computed in deterministic logarithmic space and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We show that the partitioning procedure is in logarithmic space. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best-bound known is UL $\cap$ coUL and, therefore not known to be contained in LogDCFL.

There was a mistake in the statement of the main theorem and in its proof which is now fixed, along with some minor changes.

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be solved in LogDCFL thus by a result of Cook, yielding a space-efficient ($O(\log^2{n})$-space) and polynomial time algorithm for the problem. It also yields a highly parallel algorithm (simultaneously $O(\log {n})$-time with polynomially many processors).

This generalises the previous bound of LogDCFL on one input face planar circuits. More precisely, we show that if a monotone circuit is embedded on a surface of genus $g$ and has $k$ faces on which all the inputs are present, then the circuit can be evaluated on a CROW-PRAM (concurrent read \emph{owner} write parallel random access machine) in time $O(g\log (k+g) \log{n})$ using $n^{O(1)}$ many processors.

Our main technical idea is a distance metric in single sink DAGs that can be computed in deterministic logarithmic space and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We show that the partitioning procedure is in logarithmic space. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best-bound known is UL\cap coUL and, therefore not known to be contained in LogDCFL.