On the Degree of Boolean Functions as Polynomials over ℤ_m

摘要: Polynomial representations of Boolean functions over various rings such as ℤ and ℤ_m have been studied since Minsky Papert (1969). From then on, they employed in a large variety areas including communication complexity, circuit learning theory, coding theory so on. For any integer m ≥ 2, each function has unique multilinear polynomial representation ring ℤ_m. The degree is called modulo-m degree, denoted deg_m(⋅). In this paper, we investigate the lower bound functions. When = p^k (k 1) for some prime p, give tight deg_m(f) k(p-1) non-degenerate f:{0,1}ⁿ → {0,1}, provided that n sufficient large. contains two different factors p q, nearly optimal symmetric {0,1} n/{2+1/(p-1)+1/(q-1)}.