Representing Symmetric Boolean Functions with Polynomial over Composite Moduli

蔡錫鈞(SHI-CHUN TSAI) ； 楊名全(MING-CHUAN YANG)

《Journal of Information Science and Engineering》 34卷1期 (2018/01) Pp. 193-203

https://doi.org/10.6688/JISE.2018.34.1.12

摘要

Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial P∈Z_m[x] is a generalized representation of f over Z_m if The equation is abbreviated. 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 (The equation is abbreviated) A polynomial Q∈Z_m[x] is a one-sided representation of f over Z_m if The equation is abbreviated. 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 (The equation is abbreviated) and (The equation is abbreviated) is true.

關鍵字

degree lower bound ； polynomial method ； Boolean function complexity ； ACC^0[m] circuits ； modulo degree complexity ； multivariate polynomial ； Möbius inversion ； binomial coefficient