## 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 coefficents modulo m, we prove two new lower bounds on the MOD_{m}-degree of the MOD_{1} and -MOD_{m} functions where m is any composite integer and l has a prime factor not dividing m. Both bounds improve from n^{Ω(1)} to Ω(n). With the periodic property we simplify and generalize the proof of a lower bound on the MOD_{m}-degree with symmetric multilinear polynomial of the OR function. We also prove a lower bound n/2 for the majority function and a lower bound √n for the MidBit function.

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

Title of host publication | Proceedings of the Eighth Annual Structure in Complexity Theory Conference |

Editors | Anon |

Publisher | Publ by IEEE |

Pages | 96-101 |

Number of pages | 6 |

ISBN (Print) | 0818640715 |

DOIs | |

State | Published - 1993 |

Event | Proceedings of the Eighth Annual Structure in Complexity Theory Conference - San Diego, California Duration: 18 May 1993 → 21 May 1993 |

### Publication series

Name | Proceedings of the Eighth Annual Structure in Complexity Theory Conference |
---|

### Conference

Conference | Proceedings of the Eighth Annual Structure in Complexity Theory Conference |
---|---|

City | San Diego, California |

Period | 18/05/93 → 21/05/93 |

## Fingerprint

Dive into the research topics of 'Lower bounds on representing Boolean functions as polynomials in Z_{m}'. Together they form a unique fingerprint.