# 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 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 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 circuits of constant depth and polynomial size.

The idea of the proof is by approximating ACC circuits with low-degree polynomials over GF, 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. Recall that, GF 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 of degree $$2l$$ that differs from OR on at most $$\frac{1}{2^l}$$ fraction of inputs.

### Approximate ACC Circuits by Polynomials

Given an ACC circuit, we construct a low-degree approximate polynomial. In particular, for an $$n$$-input ACC 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.