Representing Symmetric Boolean Functions with Polynomial over Composite Moduli

Abstract

Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial P is an element of Z(m)[x] is a generalized representation off over Z(m) if for all x, y is an element of{0, 1}(n); f(x)not equal f(y)double right arrow P(x)not equal 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(1) and m(2) be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n. A polynomial Q is an element of Z(m)[x] is a one-sided representation off over Z(m) if for all xe {0, 1}(n); f(x)=0 double left right arrow 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(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n and m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(-f))(t)> n is true.