Lower Bounds Against Circuits with Modular Gates

The modular gate MODm, for any integer $$m$$, outputs 0 if the sum of its inputs is 0 modulo $$m$$, and outputs 1 otherwise. An ACC[m] circuit is a circuit with NOT gates and unbounded fan-in AND, OR, and MODm gates.

ACC circuits extend AC circuits with modular gates. The parity function is not computable by AC circuits of constant depth and polynomial size. In contrast, ACC[2] circuits, which has MOD2 gates, can compute parity trivially.

The power of ACC[p] circuits is still limited if we require p to be prime. For example, parity is not computable by ACC[3] circuits of constant depth and polynomial size. In general, for two distinct prime numbers p and q, MODp is not computable by ACC[q] of constant depth and polynomial size.

Theorem. (Razborov-Smolensky)
Parity is not computable by ACC[3] circuits of constant depth and polynomial size.

The idea of the proof is by approximating ACC[3] circuits with low-degree polynomials over GF[3], and arguing that parity can not be approximated by such polynomials.

Approximate AND/OR by Polynomials

We first show that AND and OR gates can be approximated with low-degree polynomials over GF[3]. Recall that, GF[3] has elements -1, 0, 1 and $$(-1)^2 = 1^2 = 1$$ and $$0^2 = 0$$.

Without loss of generality, consider an OR gate on $$k$$ inputs $$x_1,\ldots, x_k$$. Trivially, OR can be computed exactly by a polynomial $$1- \prod (1 – x_i)$$ of degree $$k$$, but the degree is $$k$$.

Choose a random subset $$I\subseteq [k]$$, and consider the $$\sum_{i\in I} x_i$$.

• If the OR of $$x_1,\ldots, x_k$$ is 0, then $$\sum_{i\in I} x_i = 0$$.
• If the OR of $$x_1,\ldots, x_k$$ is 1, then $${\bf Pr}[ \sum_{i\in I} x_i = 0] \leq 1/2$$.

Now we choose $$l$$ random subsets $$I_1,\ldots, I_l\subseteq [k]$$ independently, and compute the following polynomial of degree $$2l$$:
$p(x_1,\ldots,x_k) = 1- \prod_{j=1}^l (1 - (\sum_{i\in I_j }x_i)^2 ).$

• If the OR of $$x_1,\ldots, x_k$$ is 0, then $$p(x)$$ is 0.
• If the OR of $$x_1,\ldots, x_k$$ is 1, then $$p(x)$$ is 0 with probability at most $$1/2^l$$.

This holds for any inputs $$x = (x_1, \ldots, x_k)$$, and also for a random $$x \in\{0,1\}^k$$. That is
${\bf Pr}_x {\bf Pr}_p [ p(x) \neq OR(x) ] \leq \frac{1}{2^l}.$
By switching the order of summation,
${\bf Pr}_p {\bf Pr}_x [ p(x) \neq OR(x) ] \leq \frac{1}{2^l}.$
Therefore, there exists a particular polynomial $$p$$ (a choice of $$l$$ subsets of $$[k]$$) such that
${\bf Pr}_x [ p(x) \neq OR(x) ] \leq \frac{1}{2^l}.$

That is, for any integer $$l$$, there is a polynomial over GF[3] of degree $$2l$$ that differs from OR on at most $$\frac{1}{2^l}$$ fraction of inputs.

Approximate ACC[3] Circuits by Polynomials

Given an ACC[3] circuit, we construct a low-degree approximate polynomial. In particular, for an $$n$$-input ACC[3] circuit of depth $$d$$ and size $$S$$, for any integer $$l$$, we can obtain a polynomial of degree $$(2l)^d$$ that differs with the circuit on only $$\frac{S}{2^l}$$ fraction of inputs.

We approximate each gate of the circuit level by level from the bottom. At depth 0, each input gate is a polynomial of degree 1. Suppose at depth $$d-1$$, each gate is approximated by a polynomial of degree $$(2l)^{d-1}$$. Consider each gate $$g$$ at depth $$d$$.

• If $$g$$ is a NOT gate, and its input gate $$f$$ is approximated by a polynomial $$f’$$, then approximate $$g$$ with $$1-f’$$. This introduces no error and no change in the degree.
• If $$g$$ is a MOD3 gate, and its input gate $$f_1,\ldots,f_k$$ are approximated by polynomials $$f_1′, \ldots, f_k’$$, then approximate $$g$$ with $$f_1′ + \cdots, f_k’$$. This introduces no error and no change in the degree.
• If $$g$$ is an AND or OR gate, and its input gate $$f_1,\ldots,f_k$$ are approximated by polynomials $$f_1′, \ldots, f_k’$$, then approximate $$g$$ using the above construction by a polynomial $$g’(f_1′, \ldots, f_k’)$$. Since each $$f_i’$$ has degree $$(2l)^{d-1}$$, the degree of $$g’$$ is at most $$(2l)^d$$. We also have $$g’$$ differs from OR of $$f_1′, \ldots, f_k’$$ on at most $$\frac{1}{2^l}$$ fraction of inputs. (Note that, here the argument also works for the inputs $$x_1,\ldots, x_n$$.)

Therefore, for the top output gate, we obtain an approximate polynomial of degree $$(2l)^d$$. At each gate, the approximation may introduces errors in $$\frac{1}{2^l}$$ fraction of inputs, and since there are totally $$S$$ gates, by the union bound, the error introduced in the output gate is on at most $$\frac{S}{2^l}$$ fraction of the inputs.

In particular, if we let $$(2l)^d = \sqrt{n}$$, then we have a degree $$\sqrt{n}$$ polynomial that differs from the circuit on at most $$S/2^{n^{1/2d}/2}$$ fraction of the inputs.

Parity Cannot be Approximated Well

Lemma.
Any polynomial over GF[3] of degree $$\sqrt{n}$$ agrees with parity on at most $$c<1$$ fraction of the inputs for some constant $$c$$.

The proof is by contradiction. Suppose there is a polynomial of degree $$\sqrt{n}$$ that agrees with parity on $$c2^n$$ inputs.

We first change the variables by letting $$y_i = 1+x_i \mod 3$$, that is mapping 0 to 1 and 1 to -1. Then parity is computed by $$\prod y_i$$, which is a degree-n monomial.
$1 + (\sum x_i \mod 2 ) \equiv (\prod y_i \mod 3)$

By assumption, there is a polynomial $$g(y)$$ of degree $$\sqrt{n}$$ that agrees with $$\prod y_i$$ (of degree $$n$$) on $$c2^n$$ inputs. Let $$A$$ be the set of inputs that $$g$$ agrees with parity. Note that $$A$$ is a subset of $\latex\{-1, 1\}^n$.

Consider an arbitrary function $$f\colon A \to \{-1, 0, 1\}$$. Since any function from $$\{-1, 0, 1\}^n$$ to $$\{-1, 0, 1\}$$ can be written as a polynomial of degree $$n$$, we can write $$f$$ as such a polynomial (but we only care about the inputs in $$A$$).

On the inputs in $$A\subset \{-1, 1\}^n$$, we have $$y_i^2 =1$$ and $$\prod y_i = g(y)$$. Therefore, for every monomial over variables indexed by $$I\subseteq [n]$$,
$\prod_{i\in I} y_i = \prod_{i\in [n]} y_i \cdot \prod_{i\in [n]\setminus I} y_i = g(y) \prod_{i\in [n]\setminus I} y_i.$

Since $$g(y)$$ has degree $$\sqrt{n}$$, every monomial of degree larger than $$(n+\sqrt{n})/2$$ can be replaced by an equivalent polynomial of degree at most
$\sqrt{n}+ n - (n+\sqrt{n})/2 = (n+\sqrt{n})/2.$
Therefore, $$f$$ can be written as a polynomial of degree at most $$(n+\sqrt{n})/2$$.

The total number of distinct polynomials of degree at most $$(n+\sqrt{n})/2$$ is bounded by 3 to the power of the number of possible monomials, which is
$\sum_{i=1}^{(n+\sqrt{n})/2} {n\choose i} \leq c \cdot 2^n$
for some constant $$c < 1$$ (e.g. $$c=0.99$$).

The total number of distinct functions $$f\colon A \to \{-1, 0, 1\}$$ is bounded by $$3^{|A|}$$. Since every such function can be exactly computed by a degree $$(n+\sqrt{n})/2$$ polynomial,
$|A| \leq c \cdot 2^n.$

Conclusion

Suppose there is an ACC[3] circuit C of depth $$d$$ and size $$S$$, and it computes parity.

By the polynomial approximation, taking $$(2l)^d = \sqrt{n}$$, there is a polynomial over GF[3] of degree $$\sqrt{n}$$ that differs from C (parity) on at most $$S/2^l$$ fraction of the inputs.

Since every polynomial over GF[3] of degree $$\sqrt{n}$$ agrees with parity on at most $$c<1$$ fraction of the inputs, we get
$S/2^l = S/2^{n^{1/2d}/2} \geq 1-c,$
$S \geq (1-c) 2^{n^{1/2d}/2}.$