An exact characterization of symmetric functions in \(qAC^{0}[2]\) (Q5941440)

\(qAC^{0}[2]\) is the class of languages computable by circuits of constant depth and quasi-polynomial \((2^{\log^{O(1)}n})\) size with unbounded fan-in AND, OR, and PARITY gates. Symmetric functions are those functions that are invariant under permutations of the input variables. Thus, a symmetric function \(f_{n}: {0,1}^{n}\rightarrow{0,1}\) can also be seen as a function \(f_{n}: {0,1,\ldots,n}\rightarrow{0,1}\). We give the following characterization of symmetric functions in \(qAC^{0}[2],\) according to how \(f_{n}(x)\) changes as \(x\) grows from \(0\) to \(n.\) A symmetric function \(f=(f_{n})_{n\in N}\) is in \(qAC^{0}[2]\) if and only if \(f_{n}\) has period \(2^{t(n)}=\log^{O(1)}n\) except within both ends of length \(\log^{O(1)}n\).