22

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.

Nikhil
  • 1,354
  • 10
  • 23
  • 3
    That's interesting.... recently (http://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 00: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 04:01
  • Are there similar/any lower bound known for determinant/permanent in case of depth 3 circuits over fields of characteristic zero? – Gorav Jindal Jun 05 '14 at 15:31
  • Over characteristic zero, AFAIK, the best lower bound is $\Omega(n^2)$ for the elementary symmetric function(and also the determinant polynomial) due to Shpilka and Wigderson. Check http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaWigderson_d3-circuits.ps.gz – Nikhil Jun 08 '14 at 08:33

2 Answers2

11

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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 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 05: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
  • @Ramprasad: I think I am definitely missing something here, but a cursory search for such a result turned up this paper http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_48.pdf, where (on page 986), it says expressing the determinant as a permanent of dimension $O(n)$ is easy and the converse is open. Am I missing something here? – Nikhil Feb 15 '13 at 11:43
  • @Ramprasad Oops! I tried working out the reduction, and I take back my previous claim - I misread the reduction mentioned in the paper I linked in my last comment. I don't think it is a projection, and might yield a circuit of higher depth or introduces more variables! – Nikhil Feb 15 '13 at 14:42
  • 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
  • Curious: If $2^{\omega(f(n)}$ lower bound for DET yields a $2^{\omega(q^{-1}(f(n))}$ lower bound for PERM at depth 3, then since we have $2^{n^{\frac{1}{2}+\epsilon}}$ upper bound for DET over complex numbers (from chasm at depth $3$), we will not have a $2^{n^{\frac{1}{2}+\epsilon}}$ lower bound for PERM if $q(n) = O(n^{1+\delta})$ for some $\delta > 0$? Even if $q(n) = O(n)$, will we not achieve a $2^{n^{\frac{1}{2}+\epsilon}}$ lower bound for PERM if the lower bound for DET over cmplex is shown to be $2^{n^{\frac{1}{2}}}$? What if the $2^{n^{\frac{1}{2}}}$ lower bound for DET is tight? – Turbo May 10 '13 at 11:37
11

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.

Jeffε
  • 23,129
  • 10
  • 96
  • 163
Leonid Gurvits
  • 111
  • 2