Lower bounds on representing Boolean functions as polynomials in Zm

Shi-Chun Tsai*

*Corresponding author for this work

研究成果: Conference contribution同行評審

6 引文 斯高帕斯(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 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.

原文English
主出版物標題Proceedings of the Eighth Annual Structure in Complexity Theory Conference
編輯 Anon
發行者Publ by IEEE
頁面96-101
頁數6
ISBN(列印)0818640715
DOIs
出版狀態Published - 1 一月 1993
事件Proceedings of the Eighth Annual Structure in Complexity Theory Conference - San Diego, California
持續時間: 18 五月 199321 五月 1993

出版系列

名字Proceedings of the Eighth Annual Structure in Complexity Theory Conference

Conference

ConferenceProceedings of the Eighth Annual Structure in Complexity Theory Conference
城市San Diego, California
期間18/05/9321/05/93

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

引用此