## Abstract

Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial PZ_{m}[x] is a generalized representation of f over Z_{m} if x, y(0, 1)^{n}; f(x)f(y)P(x)≢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_{m}
^{sym}
_{1}
^{, ge} (f ))^{s} (deg_{m}
^{sym}
_{2}
^{, ge} (f ))^{t} n. A polynomial QZ_{m}[x] is a one-sided representation of f over Z_{m} if x(0, 1)^{n}; f(x)=0Q(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_{m}
^{sym}
_{1}
^{, ge} (f ))^{s} (deg_{m}
^{sym}
_{2}
^{, ge} (f ))^{t} n and m_{1}m_{2} (deg_{m}
^{sym}
_{1}
^{, ge} (f ))^{s} (deg_{m}
^{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