### Abstract

Define the MOD_{m}-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments x^{→}, F(x^{→}) = 0 iff P(x^{→}) = 0. By exploring the periodic property of the binomial coefficients modulo m, two new lower bounds on the MOD_{m}-degree of the MOD_{l} and ¬MOD_{m} functions are proved, where m is any composite integer and l has a prime factor not dividing m. Both bounds improve from sublinear to Ω(n). With the periodic property, a simple proof of a lower bound on the MOD_{m}-degree with symmetric multilinear polynomial of the OR function is given. It is also proved that the majority function has a lower bound n/2 and the MidBit function has a lower bound √n.

Original language | English |
---|---|

Pages (from-to) | 55-62 |

Number of pages | 8 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 9 |

Issue number | 1 |

DOIs | |

State | Published - 1 Jan 1996 |

### Keywords

- Boolean function complexity
- Circuit complexity
- Computational complexity