CIRCUITS CONSTRUCTED WITH MODq GATES CANNOT COMPUTE "AND" IN SUBLINEAR SIZE
Denis Thi Rien · 1994
Algebraic techniques are used to prove that any circuit constructed with MODq gates that computes the AND function must use f~(n) gates at the first level. The best bound previously known to be valid for arbitrary q was Ft(log n). Subject classifications. 68Q05, 68Q25, 68Q40.