Next: The MOD r function
Up: Applications of the Degree
Previous: Constant Degree Hypothesis
Krause and Waack , using communication-complexity techniques, showed that any
circuit, computing the ID function:
should have size at least
where SYMMETRIC is a gate, computing an arbitrary symmetric Boolean function.
Using this result, we prove:
Proof: From the result of  and from Theorem 9 the statement is immediate.
Unfortunately, the methods of  do not generalize for MODBq gates with unrestricted B's.
be two different primes.
circuit computes the 2n
-fan-in ID function, then its size is at least
<1 depends only on p