# Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = 1$?

Notice that trivially the problem lies in $\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ because $x \equiv 1\bmod{m}$ iff $x = 1$. Question is: does the problem lie in $\mathsf{AC}^0$? If so, what is the circuit witnessing this? If not, how does one prove this?

• This problem may well be trivial but I don't know the answer and would be very interested in knowing it. – SamiD Oct 30 '13 at 21:15

You can use the usual switching lemma argument. You haven't explained how you represent your input in binary, but under any reasonable encoding, the following function is AC$^0$-equivalent to your function: $$f(x_1,\ldots,x_n) = \begin{cases} 0 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 0, \\ 1 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 1, \\ ? & \text{otherwise.} \end{cases}$$ (We assume that $n$ is even.) Following these lecture notes, suppose that $f$ can be computed by a depth $d$ circuit of size $n^b$. Then a random restriction of $n - n^{1/2^d}$ inputs leaves a function of decision tree complexity at most $2^d(b+1)+1$ with probability at least $1-1/(3n)$. A calculation will probably show that this is another instance of $f$ (on a smaller input size) with probability $\Theta(1/\sqrt{n})$, and so there is some random restriction which yields both an instance of $f$ on $n^{1/2^d}$ inputs and a function with constant decision tree complexity, leading to a contradiction. The same argument should yield exponential lower bounds.
• I think the total sensitivity of this function will also be $\Theta(\sqrt{n})$, so you could probably use that to get the exponential lower bound in my answer. The result I cite there uses the Linial-Mansour-Nisan theorem, which itself uses the switching lemma + simple bounds on the spectrum of functions of low decision tree complexity. – Sasho Nikolov Oct 31 '13 at 13:52
I do not think this is in AC0 and I can show a lower bound for the related promise problem of distinguishing between $\sum x_i = 0$ and $\sum x_i = 2$, when $x \in \{-1, 1\}^n$. Similar Fourier techniques should apply to your problem, but I have not verified that. Or maybe there is a simple reduction.
Suppose there is a size $s$ depth $d$ circuit that computes a function $f: \{-1, 1\}^n \rightarrow \{0, 1\}$ such that $f(x) = \sum_i x_i$ whenever $\sum_i x_i \in \{0,2\}$. Because for a random $x$, the probability that $\sum_i x_i = 0$ is $2^{-n} {n \choose n/2} \approx n^{-1/2}$, and for each such $x$ there are $n/2$ coordinates that change the value of $f$, the total influence of $f$ is $\Omega(n^{1/2})$, which is roughly the same as majority (because you included most of majority's sensitive inputs). By a theorem of Hastad (see Colorraly 2.5 in Ryan O'Donnel's notes), this implies that
$$s \geq 2^{\Omega(n^{1/(2d-2)})}.$$