Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR22-147 | 18th November 2022 11:28

Evaluating Monotone Circuits on Surfaces

RSS-Feed




Revision #3
Authors: Samir Datta, Chetan Gupta
Accepted on: 18th November 2022 11:28
Downloads: 9
Keywords: 


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.



Changes to previous version:

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 to TR22-147 | 18th November 2022 11:28

Evaluating Monotone Circuits on Surfaces





Revision #2
Authors: Samir Datta, Chetan Gupta
Accepted on: 18th November 2022 11:28
Downloads: 5
Keywords: 


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.



Changes to previous version:

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 to TR22-147 | 18th November 2022 11:19

Evaluating Monotone Circuits on Surfaces





Revision #1
Authors: Samir Datta, Chetan Gupta
Accepted on: 18th November 2022 11:19
Downloads: 4
Keywords: 


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.



Changes to previous version:

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


Paper:

TR22-147 | 10th November 2022 16:40

Evaluating Monotone Circuits on Surfaces





TR22-147
Authors: Samir Datta, Chetan Gupta
Publication: 10th November 2022 21:19
Downloads: 59
Keywords: 


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.



ISSN 1433-8092 | Imprint