Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that

$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at ...
more >>>