<p><a href="http://cs.uni-bonn.de/~marek/publications/AELBfD3AC.ps.gz">Grigoriev and Karpinski</a> (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$. </p>

<p>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: </p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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?</p>

<p>PS: I noticed this only while making a <a href="https://www.dropbox.com/s/6am09xfpnniwu0n/lowerbounds.pdf">consolidated exposition</a> 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. </p>

CC BY-SA 3.0
2013-04-27T08:48:28.530Z
Minor itself refers to the determinant of the submatrix, does it not?
Ramprasad
CC BY-SA 3.0
2013-04-27T11:59:09.340Z
Can't we get that indirectly using the reduction from Det to Perm?
Kaveh
CC BY-SA 3.0
2013-04-27T12:21:02.107Z
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.
Ramprasad
<lower-bounds><permanent><arithmetic-circuits><determinant>
Grigoriev-Karpinski for the permanent
Ramprasad
# Grigoriev-Karpinski for the permanent

(Asked by: username_0 on 2013-04-27)

[Grigoriev and Karpinski](http://cs.uni-bonn.de/~marek/publications/AELBfD3AC.ps.gz) (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](https://www.dropbox.com/s/6am09xfpnniwu0n/lowerbounds.pdf) 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.

**Tags:** lower-bounds, permanent, arithmetic-circuits, determinant

> **Comments:**
> **username_0**: Minor itself refers to the determinant of the submatrix, does it not?  
> **username_1**: Can't we get that indirectly using the reduction from Det to Perm?  
> **username_0**: 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.  

---

## 0 answers

