A lower bound on the mod 6 degree of the OR function |
| |
Authors: | G Tardos DA Mix Barrington |
| |
Affiliation: | (1) Mathematical Institute of the Hungarian Academy of Sciences, Pf 127, Budapest, HUNGARY H-1088, tardos@cs.elte.hu, HU;(2) Computer Science Department, University of Massachusetts, Amherst, MA, USA 01003-4610, barring@cs.umass.edu, US |
| |
Abstract: | We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z
m
. In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}n, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of
O(n
1/
r
) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington
et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known
to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known
for any function of low communication complexity and any modulus not a prime power.
received 29 September 1994 |
| |
Keywords: | , Circuit complexity, modular counting, Boolean function complexity, |
本文献已被 SpringerLink 等数据库收录! |
|