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.

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the following questions : Grigoriev and Karpinski proved an $2^{\Omega{(n)}}$ lower bound for any depth-3 arithmetic circuit computing the Determinant of $n \times n$ matrices over finite fields (which I guess, also holds for the Permanent). Ryser's formula for computing the Permanent gives a depth-3 arithmetic circuit of size $O(n^2 2^n) = 2^{O(n)}$. This shows that the result is essentially tight for depth-3 circuits for the Permanent over finite fields. I have two questions:

1) Is there a depth-3 formula for the determinant analogous to Ryser's formula for the Permanent?

2) Does a lower bound on the size of arithmetic circuits computing the Determinant polynomial \textit{always} yield a lower bound for the Permanent polynomial?(Over $\mathbb{F}_2$ they are the same polynomials).

Though my question currenly is regarding these polynomials over finite fields, I would also like to know the status of these questions over arbitrary fields.

share|improve this question
3  
That's interesting.... recently (eccc.hpi-web.de/report/2013/026) a $2^{O(n^{1/2}\log n})$ upper bound has been proved over the complex numbers. So there is somehow a huge difference in characteristic zero and finite fields... –  Ryan Williams Feb 15 '13 at 0:05
    
I should have mentioned the new result. I was reading the paper and I wanted to know what can be inferred from known results for the finite field case. Will update the question to include the paper. –  Nikhil Feb 15 '13 at 4:01
add comment

2 Answers

up vote 10 down vote accepted

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open.

In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $perm_{q(n)}(Y)$, i.e. there is a certain substitution sending each variable $y_{ij}$ either to a variable $x_{k\ell}$ or a constant such that after this substitution the $q(n) \times q(n)$ permanent is computing the $n \times n$ determinant.

1) Thus Ryser's formula yields a depth 3 formula (depth does not increase under projections because the substitutions can be done on the input gates) of size $2^{O(q(n))}$ for determinant. UPDATE: As @Ramprasad points out in the comments, this only gives something nontrivial if $q(n) = o(n \log n)$, since there is a trivial depth 2 formula of size $n \cdot n! = 2^{O(n \log n)}$ for det. I am with Ramprasad in that the best I know is the reduction through ABPs, which yields $q(n)=O(n^3)$.

2) If the $m \times m$ permanent can be computed - again, over some field of characteristic not 2 - by a circuit of size $s(m)$, then $n \times n$ determinant can be computed by a circuit of size $s(q(n))$. So a lower bound of $b(n)$ on circuit-size for $det_n$ yields a lower bound of $b(q^{-1}(n))$ on circuit-size for the permanent (that's $q$ inverse, not $1/q(n)$). The above-mentioned $q(n)=O(n^3)$ yields a $b(n^{1/3})$ perm lower bound from a $b(n)$ det lower bound.

share|improve this answer
6  
Just want to point out that the determinant being a projection of a polynomially larger permanent doesn't quite yield much. The determinant of course has a trivial $n!$ sized circuit. So even showing that the $n\times n$ determinant is a projection of a $n^2\times n^2$ permanent does not yield anything non-trivial via Ryser's formula. I guess, for your proof strategy, one needs to show that the $q(n) = O(n)$, but I don't see how to get this from the usual reduction. AFAIK, no depth-3 circuit asymptotically smaller than $n!$ is known for the determinant over finite fields. –  Ramprasad Feb 15 '13 at 5:58
    
@Ramprasad: There is a projection of $DET_n$ to $PERM_{O(n)}$ in the general case over arbitrary fields right? So implementing this reduction in depth-3 is the hurdle - is that what you mean? –  Nikhil Feb 15 '13 at 11:18
1  
@Nikhil: Is there such a projection?! If that were true, then of course we would immediately have a $2^{O(n)}$ depth-3 circuit for the determinant by just using Ryser's formula (which wasn't known prior to the chasm-at-depth-3 result). The only reduction I know is to take the ABP for the determinant (whcih is $O(n^3)$-sized) and write that as a projection of a $O(n^3)$ sized permanent. I would be very surprised of a reduction to $O(n)$-sized permanent holds. –  Ramprasad Feb 15 '13 at 11:30
1  
I'm fairly sure that is a typo/error in the article (but I shall check with Manindra though). Avi Wigderson's talk (PPT) during Valiant's 60th birthday celebrations is one of the places where it was stated that improving $n!$ for the depth-3 complexity of determinant was unknown. Depth-3 circuits over finite fields is a curious example where the best upper bound for the permanent is smaller than the determinant! –  Ramprasad Feb 15 '13 at 14:49
1  
let us continue this discussion in chat –  Ramprasad Feb 15 '13 at 15:26
show 3 more comments

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On the other hand, I proved a while ago that the Waring rank of the determinant is upper bounded by (n+1)! and this might be close to the truth.

share|improve this answer
7  
I removed the advertisement. –  JɛffE Feb 16 '13 at 16:55
3  
Can you give the reference for the proof? –  Kaveh Feb 17 '13 at 1:10
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.