Home › Theory › Lower Bounds Against Circuits with Modular Gates

Lower Bounds Against Circuits with Modular Gates

Posted on Posted in Theory Tagged with ,

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