Smaller ACC0 Circuits for Symmetric Functions

The Strength of Equality Oracles in communiucation

Chapman, Williams - Smaller ACC0 Circuits for Symmetric Functions

Knownledge

• We study constant depth circuits with Mod_m gates.
• We know that constant depth Mod_q require super-polynomial size circuits to represent Mod_m (if $q$ is a prime).
• Little is known if $m$ is not a prime power.

Result

• There is a modulus $m\leq (1/\epsilon)^{2/\epsilon}$ such that every symmetric function on $n$ bits can be computed by a depth 3 MOD_m circuit of size exp($O(n^3)$).
• Let $m$ be a prime product then any symmetric function can be computed by depth-$d$ size exp($\tilde O(n^{1/(r+d-3)})$ where $r$ is the number of primes.

Setup

• Any Mod_m gate can be simulated by Mod_mn gate with a fan-in increase factor of $n$.
• Every AND of $k$ MOD_b gates can be represented by MOD_a \circ MOD_b circuit of $O(b^k)$ gates.
• There is an arithmetic circuit of size $n^{O(i^{2/d})}$ of depth $d$ computing the $i$th elementary symmetric polynomial.
• Lucas Theorem:
  • For all primes $p$ and natural numbers $n$, $\binom{n}{p^i}\mod p$ is the $i$th digit of the $p$-ary representation of $n$.

Proof

• Main Theorem: Every symmetric function $g$ has a depth-three circuit of the form MOD_5\circ MOD_6 \circ MOD_6 of size $O(\exp(n^{1/3}\log n))$
• Theorem 3.2: Let $T\subseteq [n]$ be any subset. There is a polynomial $P$ on $n$ variables of degree $O(\sqrt{n})$ that vanishes $\mod 6$.
  • Proof:
    • This uses elementary symmetric polynomials and Lucas theorem.
    • Let $e_{J}$ be the elementary symmetric polynomial.
    • For all vectors $a$, $e_{p^i}(a_1,\dots,a_n) = \binom{\sum_i a_i}{J}$.
    • Define the polynomial $p_2(y_1,\dots,y_n) = 1-\prod_{j=0}^{s-1} (1-(b_j-e_{2^j}(y))\mod 2$.
    • Now $p_2(a)=0\mod 2$ if and only if the binary representation of $\sum_i a_i$ equals $b_j$.
    • Hence, I can enforce an arbitrary subset size.
    • A similar thing exists for $\mod 3$.
• Proof of main theorem:
  • The output gate:
    • Sum over all possible choices of $T\in [n]$ such that $g(T)=1$.
    • Sum over all possible to partition $T$ into sum of $t=n^{1/3}$ parts, called $T_1,\dots,T_t\in [T]$.
  • We associate each $T_i$ with a set $S_i$ of at most $n^{2/3}$ variables.
  • We can use mod5sum to sum over the choices for $S_i$
  • We now use a EMAJ polynomial (from Theorem 3.2) to check the sets $S_i$ which is a AND \circ MOD_p for different p.
  • With the proposition we can change this to a single MOD_6 gate.
  • We replace AND by MOD_5.