Lower bounds on representing Boolean functions as polynomials in Zm

Shi-Chun Tsai*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the Eighth Annual Structure in Complexity Theory Conference
Editors Anon
PublisherPubl by IEEE
Pages96-101
Number of pages6
ISBN (Print)0818640715
DOIs
StatePublished - 1 Jan 1993
EventProceedings of the Eighth Annual Structure in Complexity Theory Conference - San Diego, California
Duration: 18 May 199321 May 1993

Publication series

NameProceedings of the Eighth Annual Structure in Complexity Theory Conference

Conference

ConferenceProceedings of the Eighth Annual Structure in Complexity Theory Conference
CitySan Diego, California
Period18/05/9321/05/93

Fingerprint Dive into the research topics of 'Lower bounds on representing Boolean functions as polynomials in Z<sub>m</sub>'. Together they form a unique fingerprint.

Cite this