JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]


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


Representing Symmetric Boolean Functions with Polynomial over Composite Moduli


SHI-CHUN TSAI AND MING-CHUAN YANG
Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan
E-mail: sctsai@cs.nctu.edu.tw; mingchuan.cs96g@g2.nctu.edu.tw


Polynomial degree is an important measure for studying the computational complexity f Boolean function. A polynomial PZm[x] is a generalized representation of f over Zm if x, y€{0, 1}n; f(x)≢f(y)⇒P(x)≢P(y)(mod m). Denote the minimum degree as degmge(f), and degmsym,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 m1 and m2 be relatively prime numbers and have s and t distinct prime factors respectively. Then we have

       m1m2(degm1sym,ge(f))s(degm2sym,ge(f))n

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

       m1m2(degm1sym,ge(f) (f))s(degm2sym,ge(f))n

and

       m1m2(degm1sym,ge(f) (f))s(degm2sym,gef))n

is true.


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

  Retrieve PDF document (JISE_201801_12.pdf)