__
TR01-067 | 18th September 2001 00:00
__

#### Polynomial Programs and the Razborov-Smolensky Method

TR01-067
Authors:

Hubie Chen
Publication: 5th October 2001 18:31

Downloads: 2544

Keywords:

**Abstract:**
Representations of boolean functions as polynomials (over rings) have

been used to establish lower bounds in complexity theory. Such

representations were used to great effect by Smolensky, who

established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)

by representing AC^0[MOD p] functions as low-degree multilinear

polynomials over fields of characteristic p. Another tool which has

yielded insight into small-depth circuit complexity classes is the

program-over-monoids model of computation, which has provided

characterizations of circuit complexity classes such as AC^0 and NC^1.

We introduce a new model of computation, the polynomial program, which

naturally unifies both the polynomial (over ring) model of computation

and the program-over-monoids model of computation. Our motivation is

to extend Smolensky's result to prove AC^0[MOD m] lower bounds, where

m is a composite with at least two distinct prime factors.

In this paper, we first study the basic properties of this new model

of computation and its relationship to previous work. Then, we show

that Smolensky's proof of the ``hardness'' of certain functions for

the polynomial model of computation has an analog in the polynomial

program model. We also prove a dichotomy theorem on finite groups,

essentially showing that a finite group G either is so

``complicated'' that every boolean function has a degree one

polynomial program over G, or is too ``simple'' in that the function

MOD p can be computed by a low-degree polynomial program over G

for at most one prime p. The property of nilpotence gives the

dividing line. This dichotomy theorem rigorously demonstrates

limitations of the Razborov-Smolensky method for polynomial programs

over finite groups.