@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",
}