CJTCS Volume 1995 Article 2

On the Weak mod m Representation of Boolean Functions

Vince Grolmusz ( Eötvös University )
21 July, 1995
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.

[] Article 1 [] Article 3
[back] Volume 1995 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997