Published by MIT Press. Copyright 1995 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**
for legitimate access to all journal articles.

Let *P* be a polynomial over the ring of mod *m* integers.
*P* *weakly represents* Boolean function *f*:{0,1}^n
-> {0,1} if there is a subset *S* of {0,1, ... ,m-1} such that
*f*(*x*)=0 if and only if *P*(*x*)is a member of
*S*. The smallest degree of polynomials *P* weakly
representing *f* is called the *weak* mod *m*
*degree* of *f*. We give here an *O*(log *n*)
lower bound for the weak degree of the generalized inner product
function GIP of Babai, Nisan, and Szegedy. This is the first
lower-bound result for the weak degree of a Boolean function that does
not deteriorate if the number of prime divisors of *m* increases.

In the second part of the paper, we give superpolynomial lower bounds for the number of monomials with nonzero coefficients in polynomials weakly representing the OR and the GIP composed with PARITY functions.

- Preformatted versions of the article
- DVI (29,864 bytes)
**PostScript**(194,840 bytes)- PDF (192,474 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj95-02.tex`, 20,253 bytes)**BIBTeX**(`cj95-02.bib`, 4,414 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 116 bytes) - Self citation in
**BIBTeX**(284 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1995.002

Article 1 Article 3

Volume 1995 Published articles

Article 1 Article 3

Volume 1995 Published articles

Last modified: 24 March 1997