@inproceedings{1d3b4b911e50413998541975cf7f10ac,

title = "Lower bounds on representing Boolean functions as polynomials in Zm",

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 coefficents modulo m, we prove two new lower bounds on the MODm-degree of the MOD1 and -MODm 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 MODm-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.",

author = "Shi-Chun Tsai",

year = "1993",

month = jan,

day = "1",

doi = "10.1109/SCT.1993.336537",

language = "English",

isbn = "0818640715",

series = "Proceedings of the Eighth Annual Structure in Complexity Theory Conference",

publisher = "Publ by IEEE",

pages = "96--101",

editor = "Anon",

booktitle = "Proceedings of the Eighth Annual Structure in Complexity Theory Conference",

note = "null ; Conference date: 18-05-1993 Through 21-05-1993",

}