Lower bounds on representing boolean functions as polynomials in Zm

Shi-Chun Tsai*

*Corresponding author for this work

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

Define the MODm-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 MODm-degree of the MODl and ¬MODm 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 MODm-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 languageEnglish
Pages (from-to)55-62
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Volume9
Issue number1
DOIs
StatePublished - 1 Jan 1996

Keywords

  • Boolean function complexity
  • Circuit complexity
  • Computational complexity

Fingerprint Dive into the research topics of 'Lower bounds on representing boolean functions as polynomials in Z<sub>m</sub>'. Together they form a unique fingerprint.

  • Cite this