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

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>>

Derandomization of Chernoff bound with union bound is already proven in many papers.
We here give another explicit version of it that obtains a construction of size
that is arbitrary close to the probabilistic nonconstructive size.

We apply this to give a new simple polynomial time constructions of
almost $k$-wise ... more >>>