Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WILLIAMS:
Reports tagged with Williams:
TR16-085 | 28th May 2016
Shiteng Chen, Periklis Papakonstantinou

#### Depth-reduction for composites

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 ... more >>>

ISSN 1433-8092 | Imprint