Title :
A lower bound on the mod 6 degree of the OR function
Author :
Tardos, Gábor ; Barrington, David A Mix
Author_Institution :
Mathematical Res. Inst., Budapest, Hungary
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 Zm. 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 P(x)≠P(y) whenever f(x)≠f(y). Barrington, Beigel, and Rudich investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n1r)/ (where r is the number of distinct primes dividing m) and a lower bound of w(1). Here we show a lower bound of Ω(log n) when m is a product of two primes and Ω(log n) 1(r-1)/ in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial, using this liberal (and, we argue, more natural) definition very little is known. While the degree is known to be Ω(log n) for the generalized inner product because of its high communication complexity, our bound is the best known for any function of low communication complexity and any modulus not a prime power
Keywords :
Boolean functions; communication complexity; polynomials; OR function; boolean variables; communication complexity; computational power; mod 6 degree; modular counting; polynomial; Boolean functions; Circuit simulation; Complexity theory; Computer science; Concurrent computing; Polynomials; Power measurement; Size measurement; Upper bound;
Conference_Titel :
Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
Conference_Location :
Tel Aviv
Print_ISBN :
0-8186-6915-2
DOI :
10.1109/ISTCS.1995.377046