ECCC-Report TR16-085https://eccc.weizmann.ac.il/report/2016/085Comments and Revisions published for TR16-085en-usSat, 28 May 2016 07:27:02 +0300
Paper TR16-085
| Depth-reduction for composites |
Shiteng Chen,
Periklis Papakonstantinou
https://eccc.weizmann.ac.il/report/2016/085We 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.Sat, 28 May 2016 07:27:02 +0300https://eccc.weizmann.ac.il/report/2016/085