10
$\begingroup$

My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?

What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant.

$\endgroup$

1 Answer 1

12
$\begingroup$

For arithmetic circuits over $\mathbb{Z}$ your argument is exactly right. The same argument works for arithmetic circuits over $\mathbb{Q}$ which don't use any fractions $a/b$ where $b$ is even.

However, the argument no longer works if you talk about arithmetic circuits over other rings, such as: general arithmetic circuits over $\mathbb{Q}$ (i.e. without the restriction above), $\mathbb{R}$, algebraic number fields, $\mathbb{C}$, or finite fields $\mathbb{F}_{q}$ with $q \neq 2$.

(This is essentially the same reason that in algebraic geometry $\mathbb{Z}$ is often considered of so-called "mixed characteristic," rather than characteristic zero.)

However, depth 3 Boolean lower bounds for circuits with {AND,OR,NOT} are less easily related to lower bounds for arithmetic circuits over $\mathbb{Z}$. (Yes, {AND,XOR} is a complete basis, but typically depth 3 circuits over {AND, OR, NOT} you consider NOT gates free, whereas implementing NOT with XOR you're then using an XOR gate, which you actually count. Similarly, although $a \vee b = \neg (\neg a \wedge \neg b)$, when you implement this single OR gate with AND and XOR, you get a little gadget of depth 3.)

The general statement is: let $f$ be a polynomial with coefficients in a ring $R$, and suppose $\varphi\colon R \to S$ is a ring homomorphism. By applying $\varphi$ to every coefficient of $f$ you get a polynomial with coefficients in $S$, which I'll denote $f_S$. Then a lower bound for computing $f_S$ by $S$-arithmetic circuits implies the same lower bound for computing $f$ by $R$-arithmetic circuits.

$\endgroup$
4
  • $\begingroup$ what is the significance of $b$ even ? $\endgroup$ Commented Nov 30, 2012 at 3:31
  • 3
    $\begingroup$ So that when you take things mod 2 $b$ has an inverse mod 2, i.e. $a/b \in \mathbb{Q}$ becomes $ab^{-1} \pmod{2}$ and the latter is well-defined. $\endgroup$ Commented Nov 30, 2012 at 4:00
  • $\begingroup$ Does it mean that proving some kind of theorem like von-division(i.e. that you do not need to divide by two) will imply circuit lower bounds over C? $\endgroup$
    – Klim
    Commented Nov 30, 2012 at 5:27
  • $\begingroup$ @Klim: No. The issue is that a circuit over C can still use irrational (or even non-real) constants, which you still can't take "mod 2." $\endgroup$ Commented Nov 30, 2012 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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