Name
Abstract | ||
|---|---|---|
We prove that constant depth circuits, with one layer of MOD
m
gates at the inputs, followed by a fixed number of layers of MOD
p
gates, where p is prime, require exponential size to compute the MOD
q
function, if q is a prime that divides neither p nor q. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/s000370050030 | Latin American Theoretical INformatics |
Keywords | DocType | Volume |
lower bound,circuit complexity | Journal | 8 |
Issue | ISSN | ISBN |
3 | 1016-3328 | 3-540-59175-3 |
Citations | PageRank | References |
4 | 0.51 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David A. Mix Barrington | 1 | 856 | 94.79 |
| Howard Straubing | 2 | 528 | 60.92 |
| DM BARRINGTON | 3 | 4 | 0.51 |