Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 12 down vote accepted

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.

share|improve this answer
    
what is the significance of $b$ even ? –  Suresh Venkat Nov 30 '12 at 3:31
3  
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. –  Joshua Grochow Nov 30 '12 at 4:00
    
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? –  Klim Nov 30 '12 at 5:27
    
@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." –  Joshua Grochow Nov 30 '12 at 5:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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