8
$\begingroup$

Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the same proofs also goes through for $\mathrm{Perm}_n$ as well. To add to this, quite a few papers in arithmetic circuit complexity state in passing that the lower bounds is for $\mathrm{Det}_n$ and $\mathrm{Perm}_n$.

As far as I can see, the proof technique of Grigoriev and Karpinski when applied to the $\mathrm{Perm}_n$ fails at a subtle technical point. Their proof (for $\mathrm{Det}_n$) uses the following fact:

If $X$ is a matrix of indeterminates, and $A$ is an arbitrary matrix, then any minor of $AX$ is a linear combination of minors of $X$.

This is not true for the permanent though. For this technical reason, the proof doesn't quite seem to go through. Perhaps there is a simple fix for this that I am missing? Or is this is a really a subtle misconception of a fair number of people?

PS: I noticed this only while making a consolidated exposition of all known lower bound proofs for myself. The exact place where Grigoriev-Karpinski fails for the $\mathrm{Perm}_n$ is in Lemma 12 of page 7 in the above write-up, or the $T_g$ operator in the original paper.

$\endgroup$
  • $\begingroup$ Minor itself refers to the determinant of the submatrix, does it not? $\endgroup$ – Ramprasad Apr 27 '13 at 8:48
  • $\begingroup$ Oh. ... Yeah, that's right. :-> $\:$ $\endgroup$ – user6973 Apr 27 '13 at 9:43
  • $\begingroup$ Incidentally, is there a term for the matrices that minors are determinants of? $\hspace{.6 in}$ $\endgroup$ – user6973 Apr 27 '13 at 9:47
  • $\begingroup$ Can't we get that indirectly using the reduction from Det to Perm? $\endgroup$ – Kaveh Apr 27 '13 at 11:59
  • 4
    $\begingroup$ No, since the best reduction (that I know of) converts an $n$-sized determinant to an $O(n^3)$-sized permanent. Grigoriev and Razborov did show a $2^{O(\sqrt{n})}$ lower bound for permanent though. My question is about a $2^{\Omega(n)}$ lower bound. $\endgroup$ – Ramprasad Apr 27 '13 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.