Abstract
Polynomial degree is an important measure for studying the computational complexity of 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 degm ge(f), and degm 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 m1 and m2 be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n. A polynomial QZm[x] is a one-sided representation of f over Zm if x(0, 1)n; f(x)=0Q(x)0(mod m). Denote the minimum degree among these Q as degm os(f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n and m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n is true.
Original language | English |
---|---|
Pages (from-to) | 193-203 |
Number of pages | 11 |
Journal | Journal of Information Science and Engineering |
Volume | 34 |
Issue number | 1 |
DOIs | |
State | Published - 1 Jan 2018 |
Keywords
- ACC[m] circuits
- Binomial coefficient
- Boolean function complexity
- Degree lower bound
- Mobius inversion
- Modulo degree complexity
- Multivariate polynomial
- Polynomial method