3
$\begingroup$

Consider the symmetric boolean function $$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$

It is implementable in $TC^0$.

Is there an $ACC^0$ implementation?

The reason I ask is there seems to be few tricks which can be deployed.

  1. Square is sum of consecutive odd numbers.

  2. Square is $0$ or $1$ mod $4$ (checkable by $\oplus$ gates).

  3. Squares are the set of the integers having odd number of divisors.

Few are available in https://proofwiki.org/wiki/Category:Square_Numbers.

But is there a finite number of tricks which capture the function and place it in $ACC^0$?

$\endgroup$
4
$\begingroup$

Suppose $x \in \{0,\dots,2n\}$. Then we have $((2n)^2 - n) + x$ is square if and only if $x=n$. This is easily seen to imply that the square function is complete for $\mathrm{TC}^0$ under $\mathrm{AC}^0$ Turing reductions.

$\endgroup$
2
  • $\begingroup$ Can you provide why the function is TC0 hard? $\endgroup$ – User2021 Mar 1 at 15:08
  • $\begingroup$ Ah it captures threshold or rather equality. $\endgroup$ – User2021 Mar 1 at 15:12

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.