Lower bounds on representing Boolean functions as polynomials in Zm

Shi-Chun Tsai

doi:10.1109/SCT.1993.336537

Lower bounds on representing Boolean functions as polynomials in Z_m

Shi-Chun Tsai^*

^*Corresponding author for this work

Institute of Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

Define the MOD_m-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 MOD_m-degree of the MOD₁ and -MOD_m 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 MOD_m-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.

Original language	English
Title of host publication	Proceedings of the Eighth Annual Structure in Complexity Theory Conference
Editors	Anon
Publisher	Publ by IEEE
Pages	96-101
Number of pages	6
ISBN (Print)	0818640715
DOIs	https://doi.org/10.1109/SCT.1993.336537
State	Published - 1993
Event	Proceedings of the Eighth Annual Structure in Complexity Theory Conference - San Diego, California Duration: 18 May 1993 → 21 May 1993

Publication series

Name	Proceedings of the Eighth Annual Structure in Complexity Theory Conference

Conference

Conference	Proceedings of the Eighth Annual Structure in Complexity Theory Conference
City	San Diego, California
Period	18/05/93 → 21/05/93

Access to Document

10.1109/SCT.1993.336537

Cite this

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

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 = "Proceedings of the Eighth Annual Structure in Complexity Theory Conference ; Conference date: 18-05-1993 Through 21-05-1993",

}

Tsai, S-C 1993, Lower bounds on representing Boolean functions as polynomials in Z_m. in Anon (ed.), Proceedings of the Eighth Annual Structure in Complexity Theory Conference. Proceedings of the Eighth Annual Structure in Complexity Theory Conference, Publ by IEEE, pp. 96-101, Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, California, 18/05/93. https://doi.org/10.1109/SCT.1993.336537

Lower bounds on representing Boolean functions as polynomials in Z_m. / Tsai, Shi-Chun.
Proceedings of the Eighth Annual Structure in Complexity Theory Conference. ed. / Anon. Publ by IEEE, 1993. p. 96-101 (Proceedings of the Eighth Annual Structure in Complexity Theory Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Tsai, Shi-Chun

PY - 1993

Y1 - 1993

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

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

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

U2 - 10.1109/SCT.1993.336537

DO - 10.1109/SCT.1993.336537

M3 - Conference contribution

AN - SCOPUS:0027309991

SN - 0818640715

T3 - Proceedings of the Eighth Annual Structure in Complexity Theory Conference

SP - 96

EP - 101

BT - Proceedings of the Eighth Annual Structure in Complexity Theory Conference

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the Eighth Annual Structure in Complexity Theory Conference

Y2 - 18 May 1993 through 21 May 1993

ER -