9
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 31 '13 at 13:52
7
$\begingroup$

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)})}. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.