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[/latex] fraction of the inputs for some constant [latex]c[/latex]. The proof is by contradiction. Suppose there is a polynomial of degree [latex]\sqrt{n}[/latex] that agrees with parity on [latex]c2^n[/latex] inputs. We first change the variables by letting [latex]y_i = 1+x_i \mod 3[/latex], that is mapping 0 to 1 and 1 to -1. Then parity is computed by [latex]\prod y_i[/latex], which is a degree-n monomial. \[ 1 + (\sum x_i \mod 2 ) \equiv (\prod y_i \mod 3) \] By assumption, there is a polynomial [latex]g(y)[/latex] of degree [latex]\sqrt{n}[/latex] that agrees with [latex]\prod y_i[/latex] (of degree [latex]n[/latex]) on [latex]c2^n[/latex] inputs. Let [latex]A[/latex] be the set of inputs that [latex]g[/latex] agrees with parity. Note that [latex]A[/latex] is a subset of $\latex\{-1, 1\}^n$. Consider an arbitrary function [latex]f\colon A \to \{-1, 0, 1\}[/latex]. Since any function from [latex]\{-1, 0, 1\}^n[/latex] to [latex]\{-1, 0, 1\}[/latex] can be written as a polynomial of degree [latex]n[/latex], we can write [latex]f[/latex] as such a polynomial (but we only care about the inputs in [latex]A[/latex]). On the inputs in [latex]A\subset \{-1, 1\}^n[/latex], we have [latex]y_i^2 =1[/latex] and [latex]\prod y_i = g(y)[/latex]. Therefore, for every monomial over variables indexed by [latex]I\subseteq [n][/latex], \[ \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 [latex]g(y)[/latex] has degree [latex]\sqrt{n}[/latex], every monomial of degree larger than [latex](n+\sqrt{n})/2[/latex] can be replaced by an equivalent polynomial of degree at most \[ \sqrt{n}+ n - (n+\sqrt{n})/2 = (n+\sqrt{n})/2$. \] Therefore, [latex]f[/latex] can be written as a polynomial of degree at most [latex](n+\sqrt{n})/2[/latex]. The total number of distinct polynomials of degree at most [latex](n+\sqrt{n})/2[/latex] 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 [latex]c < 1[/latex] (e.g. [latex]c=0.99[/latex]). The total number of distinct functions [latex]f\colon A \to \{-1, 0, 1\}[/latex] is bounded by [latex]3^{|A|}[/latex]. Since every such function can be exactly computed by a degree [latex](n+\sqrt{n})/2[/latex] polynomial, \[ |A| \leq c \cdot 2^n. \]

Conclusion

Suppose there is an ACC[3] circuit C of depth [latex]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[/latex] 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