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}.
\]

Comments

comments

Tagged with: ,
Posted in Theory