Authors: David Barrington, Richard Beigel, and Steven Rudich
Abstract: Define the MODm-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments x , F(x) = 0 iff P(x) = 0. We obtain the unexpected result that the MODm-degree of the OR of N variables is O(N1/r), where r is the number of distinct prime factors of m. This is optimal in the case of representation by symmetric polynomials. The MODn function is 0 if the number of input ones is a multiple of n and is one otherwise. We show that the MODm-degree of both the MODn and ¬MODn functions is NΩ(1) exactly when there is a prime dividing n but not m. The MODm-degree of the MODm function is 1; we show that the MODm-degree of ¬MODm is NΩ(1) if m is not a power of a prime, O(1) otherwise. A corollary is that there exists an oracle relative to which the MODmP classes (such as PARITYP) have this structure: MODmP is closed under complementation and union iff m is a prime power, and MODnP ⊆ MODmP iff all primes dividing n also divide m.
Download Full Paper