Fanout Complexity of Symmetric Boolean Functions in ${\mathsf{QAC}}^0$

Abstract

Whether ${\mathsf{QAC}}^0$ can compute ${\mathtt{PARITY}}_n$ remains open. Computing ${\mathtt{PARITY}}_n$ is equivalent to implementing ${\mathtt{FANOUT}}_n$ under ${\mathsf{QAC}}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in ${\mathsf{QAC}}^0$? We show that the answer is exactly the transition radius $\rho (f)$: computing $f$ and implementing ${\mathtt{FANOUT}}_{\rho (f)}$ are equivalent under ${\mathsf{QAC}}^0$ reductions. In particular, if $\rho (f)\ge n^{\delta }$ for some constant $\delta >0$, then computing $f$ is ${\mathsf{QAC}}_{\mathrm{f}}^0$-complete. Combined with Paturi's theorem, our characterization implies that if ${\mathtt{PARITY}}_n\notin {\mathsf{QAC}}^0$, then any Boolean function in ${\mathsf{QAC}}^0$ of approximate degree $n^{1/2+\Omega (1)}$ must be nonsymmetric.

arXiv commentcomments are welcome