ECCC-Report TR22-147https://eccc.weizmann.ac.il/report/2022/147Comments and Revisions published for TR22-147en-usFri, 18 Nov 2022 11:28:26 +0200
Revision 3
| Evaluating Monotone Circuits on Surfaces |
Chetan Gupta,
Samir Datta
https://eccc.weizmann.ac.il/report/2022/147#revision3In 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.Fri, 18 Nov 2022 11:28:26 +0200https://eccc.weizmann.ac.il/report/2022/147#revision3
Revision 2
| Evaluating Monotone Circuits on Surfaces |
Chetan Gupta,
Samir Datta
https://eccc.weizmann.ac.il/report/2022/147#revision2In 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.Fri, 18 Nov 2022 11:28:23 +0200https://eccc.weizmann.ac.il/report/2022/147#revision2
Revision 1
| Evaluating Monotone Circuits on Surfaces |
Chetan Gupta,
Samir Datta
https://eccc.weizmann.ac.il/report/2022/147#revision1In 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.Fri, 18 Nov 2022 11:19:48 +0200https://eccc.weizmann.ac.il/report/2022/147#revision1
Paper TR22-147
| Evaluating Monotone Circuits on Surfaces |
Chetan Gupta,
Samir Datta
https://eccc.weizmann.ac.il/report/2022/147In 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.Thu, 10 Nov 2022 21:19:21 +0200https://eccc.weizmann.ac.il/report/2022/147