TY - JOUR

T1 - Lower bounds on representing boolean functions as polynomials in Zm

AU - Tsai, Shi-Chun

PY - 1996/1/1

Y1 - 1996/1/1

N2 - 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.

AB - 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.

KW - Boolean function complexity

KW - Circuit complexity

KW - Computational complexity

UR - http://www.scopus.com/inward/record.url?scp=0030356505&partnerID=8YFLogxK

U2 - 10.1137/S0895480193255505

DO - 10.1137/S0895480193255505

M3 - Article

AN - SCOPUS:0030356505

VL - 9

SP - 55

EP - 62

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 1

ER -