Smaller ACC0 Circuits for Symmetric Functions

2021-07-09-CW-Smaller ACC0 Circuits for Symmetric Functions

paper

Results

• Theorem 1.1: For every $\epsilon$ and $m<(1/3)^{2/\epsilon}$ such that every symmetric function can be computed by a depth 3 circuit of form $\mod_{p_1}\circ \mod_{p_2,\dots,p_r}\circ \mod_{p_r}$ where these are distinct primes of size $\exp(O(n^{\epsilon}))$.
• Theorem 1.2: Every symmetric function can be computed by a depth $d$ $\mod_m$ circuit of size $\exp(\tilde O(n^{1/(r+d-3)}))$.
• Hypothesis (Sym And): There is a function $f$ computable by a TC$_0$ circuit with at most $\tilde O(n)$ gates with fan-in $\tilde O(n)$ such that $f$ does not have $\exp(O(n^{1/k}))$ size $\text{SYM}\circ \text{AND}$ circuits.
• ACC$_0[m]$ is the class of constant depth poly size circuits with unbounded fan-in that are allowed $\mod_m$ gates.
• Theorem 1.5: Assuming Sym And Hypothesis there is a fixed $\alpha$ such that for every $m,d$, every ACC$_0[m]$ computing the majority function has size at least $\exp(n^{\alpha/rd})$.

Proof of Theorem 1.1

Prerequisite

• Lucas Theorem: $\binom{n}{p^i}\mod p$ is the $i$th digit in the $p$-ary representation of $n$.
  • This implies that taking the elementary symmetric polynomial $e_{p^i}(a_1,\dots,a_n)\mod p$ of degree $p^i$ equals the $i$th digit in the $p$-ary representation of $\sum_i a_i$.
• Proposition 2.2(BIS90,CP19): Let $a,b$ be fixed integers with $\gcd(a,b)=1$. Every $\land\circ \mod_b$ gate can be represented by a $\mod_a\circ\mod_b$ circuit of $O(b^k)$ gates.
• Theorem 3.1 (Non Generalized form of 1.1): Every symmetric boolean function has a depth 3 circuit of the form $\mod_5 \circ \mod_6\circ \mod 5$ of size $\exp(O(n^{1/3} \log n))$.
• Theorem 3.2: For every $T\in {0,1,\dots,n}$ there exists a polynomial on $n$ variables of degree at most $3\sqrt{n}$ such that for all $a\in {0,1}^n$, $P_T(a)=0\mod 6$ if and only if $\sum_{i} a_i = T$.
• Proof:
  • Use the elementary symmetric polynomial $e_J$ of degree $J$.
  • By Lucas Theorem $e_{p^i}(a_1,\dots,a_n)\mod p$ equals the $i$th digit in the $p$-ary representation of $\sum_i a_i$.
  • We can easily check the $p$-ary representation with a $\mod_p$ polynomial.
  • This is just $p_q(a_1,\dots,a_n) =1 - \prod_{j=0}^{t-1} (1-(c_j -e_{q^i})^{q-1})$.
  • Doing this for $s,t$ and primes $2,3$ such that $2^s\cdot 3^t>n$ we get the required polynomial.

Proof of Theorem 3.1:

• Let $f$ be our function.
• We define $g:[n]\rightarrow {0,1}$ as $f(x)=g(|x|_1)$.
• The output gate sums over (a) all possible choices of $T\in [n]$ such that $g(T)=1$ and (b) sums over all ways to partition $T$ into a sum of $\lceil n^{1/3}\rceil$ many parts $T_1,\dots,T_{t} \in [T]$.
• There are $2^{O(n^{1/3}\log n)}$ many choices.
• Associate each $T_i$ with a disjoint set $S_i$ of at most $\lceil n^{2/3}\rceil$ many input variables.
• We want to verify that each $T_i$ the sum over the variables in $S_i$ equals $T_i$.
• Notice that there is at most one choice from (a) and (b) that could be consistent with the given input.
  • This is clear, as the sets and size describe it.
• Hence, we can sum over these choices by using a $\mod_5$ gate, as the value is either $0$ or $1$.
• That means we now have a given size $T_i$ and $S_i$. We already checked that $T_i$ corresponds to $|S_i|$ on the second layer.
• We now check that the set is correct by an $\mod_6\circ$ $\land$ gate.
  • For this we use Theorem 3.2.
  • As the polynomial has degree $\sqrt{n}$, we can simulate it by a $\mod_6$ gate over the monomials represented by and $\land$ gate.
  • As this uses something like Chinese Remainder, we need another $\land$ gate.
• This gives us a circuit $\mod_6\circ \mod_5\circ \land \circ \mod_6 \circ \land$.
• Now Proposition 2.2 eliminates the $\land$ gate.
  • Note: While this is the original as written in the paper, I do not quite understand the application of it.
  • However, there is a SYM$\circ\land$ which they reference and gives subexponential size.
  • The new size of the proposition is then $2^{(\log n)^d}$.
  • This stays inside the overall size bound.
• Proof Sketch of Theorem 1.1:
  • The proof works similar, except that we partition the sum into $n^{1/k}$ parts and use Chinese Remainder.

Proof of Theorem 1.5

• Contraposition: Assume there is some $m=p_1\cdot p_r$ along with depth $d$ such that majority can be computed by depth-$d$ ACC$_0[m]$ circuit of size $\exp(O(n^{\alpha/rd}))$.
• Let $C$ be a TC$_0$ circuit.
• Replace every majority gate with a copy of the assumed circuit.
• This gives us a ACC$_0[m]$ circuit of depth at most $cd$ and size $\exp(O(n^{\alpha/rd}))$.
• By (CP19) every depth $cd$ circuit of size $s$ over $\land,\lor,\mod_m$ gates is equivalent to a SYM$\circ\land$ circuit of size $D'$ with $2^{(m\log s)^{10rcd}}$.
• This gives us the contradiction.