Mod q
Definition
Let [math]q[/math] be a positive integer. The [math]n[/math] variable mod q function is the Boolean function [math]f:\{-1,1\}^n\to\{-1,1\}[/math] defined by
[math] f(x) = \begin{cases} -1, & if ~ \#\{i \mid x_i = 1\} = 0 & (\mathrm{mod} ~ q) \\ 1 & otherwise \end{cases}[/math]
In words, [math]f(x)=-1[/math] if and only if the number of ones in the vector [math]x\in\{-1,1\}^n[/math] is divisible by [math]q[/math].
For [math]q=2[/math], this is the parity function.
Properties
- Mod q is not in AC0: For a given prime [math]p[/math], a depth [math]d[/math] circuit which uses only NOT, OR and mod-p gates requires at least [math]\exp O(n^{1/2d})[/math] gates in order to compute the function mod-q for any [math]q \neq p^m[/math]. [1]
References
- ↑ R. Smolensky. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 77-82. DOI=http://dx.doi.org/10.1145/28395.28404
