<p>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. </p>

<p>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 <a href="http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture10.pdf">notes</a>), this implies that </p>

<p>$$
s \geq 2^{\Omega(n^{1/(2d-2)})}.
$$</p>

CC BY-SA 3.0
2013-10-30T22:21:19.050Z
2013-10-30T23:54:37.473Z
2013-10-30T23:54:37.473Z
Sasho Nikolov
<p>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 &amp; \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 0, \\ 1 &amp; \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 1, \\ ? &amp; \text{otherwise.} \end{cases} $$
(We assume that $n$ is even.) Following <a href="http://www.cs.princeton.edu/courses/archive/spr01/cs522/lecnotes/lec19.ps">these lecture notes</a>, 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.</p>

CC BY-SA 3.0
2013-10-31T13:52:34.923Z
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
CC BY-SA 3.0
2013-10-31T07:19:38.660Z
2013-10-31T07:29:14.193Z
2013-10-31T07:29:14.193Z
Yuval Filmus
<p>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$?</p>

<p>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?</p>

CC BY-SA 3.0
2013-10-30T21:15:38.530Z
This problem may well be trivial but I don't know the answer and would be very interested in knowing it.
SamiD
<reference-request><complexity-classes><circuit-complexity><upper-bounds>
Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$
SamiD
# Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

(Asked by: username_0 on 2013-10-30)

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?

**Tags:** reference-request, complexity-classes, circuit-complexity, upper-bounds
> **Comments:**
> **username_0**: This problem may well be trivial but I don't know the answer and would be very interested in knowing it.  

---

## 2 answers

### Answer by username_2 on 2013-10-31. Score: 7 | Accepted answer

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](http://www.cs.princeton.edu/courses/archive/spr01/cs522/lecnotes/lec19.ps), 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.

> **Comments:**
> **username_1**: 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.  

---

### Answer by username_1 on 2013-10-30. Score: 7

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](http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture10.pdf)), this implies that

$$
s \geq 2^{\Omega(n^{1/(2d-2)})}.
$$


---

