Chicago Journal of Theoretical Computer Science

Volume 1995

Article 2

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.

On the Weak mod m Representation of Boolean Functions

Vince Grolmusz (Eötvös University)
21 July, 1995

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.

DOI: 10.4086/cjtcs.1995.002
[] Article 1 [] Article 3
[back] Volume 1995 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997