# 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.

Lemma.