Lower bounds on representing boolean functions as polynomials in Zm

Shi-Chun Tsai*

*此作品的通信作者

研究成果: Article同行評審

18 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)55-62
頁數8
期刊SIAM Journal on Discrete Mathematics
9
發行號1
DOIs
出版狀態Published - 1 一月 1996

指紋

深入研究「Lower bounds on representing boolean functions as polynomials in Z<sub>m</sub>」主題。共同形成了獨特的指紋。

引用此