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.

Parity Cannot be Approximated Well

Lemma.
Any polynomial over GF 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 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 of degree $$\sqrt{n}$$ that differs from C (parity) on at most $$S/2^l$$ fraction of the inputs.

Since every polynomial over GF 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}.$