JISE

Polynomial degree is an important measure for studying the computational complexity f Boolean function. A polynomial P€Z_m[x] is a generalized representation of f over Z_m if x, y€{0, 1}ⁿ; f(x)≢f(y)⇒P(x)≢P(y)(mod m). Denote the minimum degree as deg_m^ge(f), and deg_m^sym,ge(f) if the minimum is taken from symmetric polynomials. In this paper we prove new lower bounds for the symmetric Boolean functions that depend on n variables. First, let m₁ and m₂ be relatively prime numbers and have s and t distinct prime factors respectively. Then we have

       m₁m₂(deg_m1^sym,ge(f))^s(deg_m2^sym,ge(f))^t > n

A polynomial Q€Z_m[x] is a one-sided representation of f over Z_m if x€{0, 1}ⁿ; f(x)≢0⇔Q(x)=0(mod m). Denote the minimum degree among these Q as deg_m^os(f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of

       m₁m₂(deg_m1^sym,ge(f) (f))^s(deg_m2^sym,ge(f))^t > n

and

       m₁m₂(deg_m1^sym,ge(f) (f))^s(deg_m2^sym,ge(¬f))^t > n

is true.