Abstract
A prefix-or circuit has n inputs and n outputs; the ith output is the OR of the first i inputs. A prefix-carry circuit has 2n inputs, interpreted as two n-bit numbers, and n outputs; the ith output is the carry in the ith position of the sum of the two numbers. We show a nonlinear lower bound for constant-depth, unboundedfanin implementations of prefix-or. However, with negation, linear size circuits are possible. For prefix-carry, we show nonlinear lower bounds for arbitrary circuits. In both cases the lower bounds exhibit a size/depth tradeoff: the circuit size must be at least Ω(nf −1 d d(n)) for depth a constant times d. Here the functions f d form an increasing hierarchy coextensive with the primitive recursive functions. The lower bounds match the known upper bounds for these problems, to within a constant factor for depth.
Research supported by DARPA contract N00014082-K-0549.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Bibliography
S. Cook and C. Dwork,“Bounds on the Time for Parallel RAM's to Compute Simple Functions,” Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, 231–233.
A.K. Chandra, S.J. Fortune, R. Lipton, “Unbounded Fanin Circuits and Associative Functions,” Proceedings of the 15th ACM Symposium on Theory of Computing, 1983.
A.K. Chandra, L.J. Stockmeyer, U. Vishkin, “A Complexity Theory for Unbounded Fan-in Parallelism,” Proceedings 23rd Annual Symposium on the Foundations of Computer Science, 1982, pp. 1–13.
D. Dolev, C. Dwork, N. Pippenger, A. Wigderson, “Superconcentrators, Generalizers and Generalized Connectors with Limited Depth,” Proceedings of the 15th ACM Symposium on Theory of Computing, 1983.
M. Furst, J. Saxe, M. Sipser, “Parity, Circuits, and the Polynomial-time Hierarchy,” Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science, 1981, pp. 260–270.
O. Gabber and Z. Galil, “Explicit Constructions of Linear Size Concentrators,” Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, 1979, pp. 364–370.
L.M. Goldschlager, “A Unified Approach to Models of Synchronous Parallel Machines,” Proceedings of the Tenth ACM Symposium on Theory of Computing, 1978, pp. 89–94.
F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass, 1971.
R. McNaughton, S. Papert, Counter-Free Automata, Research Monograph No. 65, The MIT Press, Cambridge, Mass., 1971.
R. Reischuk, “A Lower Time Bound for Parallel Random Access Machines without Simultaneous Writes,” Report RJ3431, IBM Research Lab, San Jose, Ca, 1982.
Y. Shiloach and U. Vishkin, “Finding the Maximum, Merging, and Sorting in a Parallel Computation Model,” J. of Algorithms 2 (1981), pp. 88–102.
L.G. Valiant, “On Non-linear Lower Bounds in Computational Complexity,” Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 45–53.
U. Vishkin “Implementation of Simultaneous Memory Access in Models that Forbid it,” Tech Report No 210, Dept of Computer Science, Technion, Haifa, Israel, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1983 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chandra, A.K., Fortune, S., Lipton, R. (1983). Lower bounds for constant depth circuits for prefix problems. In: Diaz, J. (eds) Automata, Languages and Programming. ICALP 1983. Lecture Notes in Computer Science, vol 154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036901
Download citation
DOI: https://doi.org/10.1007/BFb0036901
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-12317-0
Online ISBN: 978-3-540-40038-7
eBook Packages: Springer Book Archive