Abstract.
We prove that constant depth circuits, with one layer of M O D m gates at the inputs, followed by a fixed number of layers of M O D p gates, where p is prime, require exponential size to compute the M O D q function, if q is a prime that divides neither p nor m.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: January 23, 1998.
Rights and permissions
About this article
Cite this article
Mix Barrington, D., Straubing, H. Lower bounds for modular counting by circuits with modular gates. Comput. complex. 8, 258–272 (1999). https://doi.org/10.1007/s000370050030
Issue Date:
DOI: https://doi.org/10.1007/s000370050030