Revision #3 Authors: Samir Datta, Chetan Gupta

Accepted on: 18th November 2022 11:28

Downloads: 139

Keywords:

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.

Revision #2 Authors: Samir Datta, Chetan Gupta

Accepted on: 18th November 2022 11:28

Downloads: 116

Keywords:

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.

Revision #1 Authors: Samir Datta, Chetan Gupta

Accepted on: 18th November 2022 11:19

Downloads: 118

Keywords:

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.

TR22-147 Authors: Samir Datta, Chetan Gupta

Publication: 10th November 2022 21:19

Downloads: 196

Keywords:

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.