On the Weak mod m Representation of Boolean Functions
Vince I. Grolmusz · 1995
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : {0, 1} n #{0,1} if there is a subset S #{0,1,... ,m-1}such that f(x) = 0 if and only if P (x) # S. The smallest degree of polynomials P weakly representing f is called the weak mod m degree of f . We give here an Omega(log n) lower bound for the weak degree of the generalized inner product function (GIP) of Babai, Nisan, and Szegedy [BNS92]. This is the first lower-bound result for the weak degree of a Boolean function that does not deteriorate if the number of prime divisors of m increases. In the second part of the paper, we give superpolynomial lower bounds for the number of monomials with nonzero coefficients in polynomials weakly representing the OR and the GIPoPARITY functions.