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.

Abstract

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

Last modified: 24 March 1997