Lower bounds for modular counting by circuits with modular gates |
| |
| Authors: | D. A. Mix Barrington H. Straubing |
| |
| Affiliation: | (1) Computer Science Department, University of Massachusetts, Amherst, MA 01003, USA, e-mail: barrington@cs.umass.edu, US;(2) Computer Science Department, Boston College, Chestnut Hill, MA 02167, USA, e-mail: straubing@bc.edu, US |
| |
| 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. Received: January 23, 1998. |
| |
| Keywords: | . Circuit complexity modular counting. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
