Journal of Information Science and Engineering, Vol. 34 No. 1, pp. 193-203

Representing Symmetric Boolean Functions with Polynomial over Composite Moduli

Polynomial degree is an important measure for studying the computational complexity *f* Boolean function. A polynomial ** P**€

*m*_{1}*m*_{2}(deg_{m1}* ^{sym,ge}*(

A polynomial *Q*€*Z*_{m}[** x**] is a

*m*_{1}*m*_{2}(deg_{m1}* ^{sym,ge}*(

and

*m*_{1}*m*_{2}(deg_{m1}* ^{sym,ge}*(

is true.

Keywords:
degree lower bound, polynomial method, Boolean function complexity, ACC0[m]
circuits, modulo degree complexity, multivariate polynomial, Möbius inversion, binomial
coefficient