TR16-085 Authors: Shiteng Chen, Periklis Papakonstantinou

Publication: 28th May 2016 07:27

Downloads: 2162

Keywords:

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of size $2^{{(\log n)}^{O(d)}}$. This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup $2^{{(\log n)}^{2^{O(d)}}}$. Therefore, depth-reduction for composite $m$ matches the size of the Allender-Hertrampf construction for primes from 1989.

One immediate implication of depth reduction is an improvement of the depth from $o(\log\log n)$ to $o(\log n/\log\log n)$, in Williams' program for $ACC$ circuit lower bounds against $NEXP$. This is just short of $O(\log n/\log\log n)$ and thus pushes William's program to the $NC^1$ barrier, since $NC^1$ is contained in $ACC$ of depth $O(\log n/\log\log n)$. A second, but non-immediate, implication regards the strengthening of the $ACC$ lower bound in the Chattopadhyay-Santhanam interactive compression setting.