<p>It depends a little what you mean exactly by &quot;GCT&quot;. If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question.</p>
<p>If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using geometry to cross the GCT chasm, as in this quote:</p>
<blockquote>
<p>By geometric complexity theory, we mean henceforth any approach to cross the GCT chasm using asynthesis of geometry and complexity theory. -Mulmuley, <a href="http://dx.doi.org/10.1090/jams/864" rel="noreferrer">GCT V</a> <a href="https://arxiv.org/abs/1209.5993" rel="noreferrer">arXiv</a></p>
</blockquote>
<p>Then the answer is that algebraic geometry can certainly prove positive results in complexity theory. First in principle: <span class="math-container">$\mathsf{VNP} \nsubseteq \overline{\mathsf{VP}}$</span> if and only if there is a polynomial vanishing on the latter but not on the former - this is very basic algebraic geometry. Similar results hold whenever one considers the approximative/border/closure of a complexity class. Second, in history: border-rank methods are algebro-geometric, and have yielded new algorithms for matrix multiplication, as well as results relating the complexity of a polynomial to those of its factors <a href="https://doi.org/10.1007/s10208-002-0059-5" rel="noreferrer">Bürgisser</a> (<a href="https://arxiv.org/abs/1812.06828" rel="noreferrer">arXiv</a>)</p>
<p>If, on the other hand, you mean more specifically separating complexity classes using multiplicity obstructions, then your question gets at the &quot;converse&quot; question in GCT: that is, it is a theorem that a multiplicity obstruction implies a separation of complexity classes, but is the converse true? In general for <span class="math-container">$G$</span>-varieties this is almost certainly false (that is, given a reductive algebraic group <span class="math-container">$G$</span> like <span class="math-container">$GL_n$</span> acting algebraically on a vector space <span class="math-container">$V$</span>, and two varieties <span class="math-container">$X,Y \subseteq V$</span> that are each unions of <span class="math-container">$G$</span>-orbits, is it the case that <span class="math-container">$X \subseteq Y$</span> iff there are no multiplicity obstructions?). But for the particular varieties of interest in GCT, there is some chance that the converse might hold. A first indication of this is that the polynomials studied are characterized by their symmetries, which already tells you that the group action here is telling you more about these particular varieties than it would be for general <span class="math-container">$G$</span>-varieties.</p>
<p>If the converse held, then one could in principle get a collapse of complexity classes by proving that there were no multiplicity obstructions. On the one hand, this seems quite hard. On the other hand, <a href="https://doi.org/10.1090/jams/908" rel="noreferrer">Bürgisser-Ikenmeyer-Panova</a> (<a href="https://arxiv.org/abs/1604.06431" rel="noreferrer">arXiv</a>) proved that there were no occurrence obstructions (multiplicty zero in one class and nonzero in the other).</p>
<p>However, even if the converse didn't hold, knowing that there were no multiplicity obstructions would still, I think, yield significant insight into the relationship between these problems. Each representation of <span class="math-container">$GL_{n^2}$</span> appearing in the ring of (meta)polynomials (a polynomial ring in a number of variables that is equal to the number of monomials of degree <span class="math-container">$n$</span> in <span class="math-container">$n^2$</span> variables) corresponds to a <span class="math-container">$GL_{n^2}$</span>-invariant property of (ordinary) polynomials. The isomorphism type of such a representation tells you how its defining equations transform under the action of <span class="math-container">$GL_{n^2}$</span>. The multiplicity of a given isomorphism type (isotype) in the coordinate ring of one of these varieties <span class="math-container">$X$</span> thus tells you how many properties of that isotype the polynomials in <span class="math-container">$X$</span> have. Knowing that there were no multiplicity obstructions would still imply that these complexity classes share many more properties than one might initially think.</p>

CC BY-SA 4.0
2021-02-19T04:16:38.147Z
2021-02-19T04:16:38.147Z
Joshua Grochow
<p><span class="math-container">$GCT$</span> is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would <span class="math-container">$GCT$</span> be a program which can provide the insight? Is so how would the hypothetical demonstration be?</p>

CC BY-SA 4.0
2021-02-18T12:43:13.823Z
There is an abusive moderator.
Turbo
CC BY-SA 4.0
2021-02-19T04:18:02.803Z
I don't really understand the downvotes. I'd encourage the people who did so to leave a constructive comment, but my guess is that they downvoted and then unfortunately won't ever visit the question again.
Joshua Grochow
CC BY-SA 4.0
2021-02-19T07:19:09.287Z
I agree with @JoshuaGrochow's comment and I'd also encourage more upvoting. That said, people are free to vote up and down content they like or do not like, I believe such are still the rules on this site. In any case, this is about users voting and not about moderators as far as I can see.
Bjørn Kjos-Hanssen
<cc.complexity-theory><ds.algorithms><big-picture><algebraic-complexity><symmetry>
Is $GCT$ necessarily a negative result program?
Turbo
# Is $GCT$ necessarily a negative result program?

(Asked by: username_0 on 2021-02-18)

$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can provide the insight? Is so how would the hypothetical demonstration be?

**Tags:** cc.complexity-theory, ds.algorithms, big-picture, algebraic-complexity, symmetry
> **Comments:**
> **username_0**: There is an abusive moderator.  
> **username_1**: I don't really understand the downvotes. I'd encourage the people who did so to leave a constructive comment, but my guess is that they downvoted and then unfortunately won't ever visit the question again.  
> **username_2**: I agree with @JoshuaGrochow's comment and I'd also encourage more upvoting. That said, people are free to vote up and down content they like or do not like, I believe such are still the rules on this site. In any case, this is about users voting and not about moderators as far as I can see.  

---

## 1 answers

### Answer by username_1 on 2021-02-19. Score: 5 | Accepted answer

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question.

If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using geometry to cross the GCT chasm, as in this quote:

> By geometric complexity theory, we mean henceforth any approach to cross the GCT chasm using asynthesis of geometry and complexity theory. -Mulmuley, [GCT V](http://dx.doi.org/10.1090/jams/864) [arXiv](https://arxiv.org/abs/1209.5993)

Then the answer is that algebraic geometry can certainly prove positive results in complexity theory. First in principle: $\mathsf{VNP} \nsubseteq \overline{\mathsf{VP}}$ if and only if there is a polynomial vanishing on the latter but not on the former - this is very basic algebraic geometry. Similar results hold whenever one considers the approximative/border/closure of a complexity class. Second, in history: border-rank methods are algebro-geometric, and have yielded new algorithms for matrix multiplication, as well as results relating the complexity of a polynomial to those of its factors [Bürgisser](https://doi.org/10.1007/s10208-002-0059-5) ([arXiv](https://arxiv.org/abs/1812.06828))

If, on the other hand, you mean more specifically separating complexity classes using multiplicity obstructions, then your question gets at the "converse" question in GCT: that is, it is a theorem that a multiplicity obstruction implies a separation of complexity classes, but is the converse true? In general for $G$-varieties this is almost certainly false (that is, given a reductive algebraic group $G$ like $GL\_n$ acting algebraically on a vector space $V$, and two varieties $X,Y \subseteq V$ that are each unions of $G$-orbits, is it the case that $X \subseteq Y$ iff there are no multiplicity obstructions?). But for the particular varieties of interest in GCT, there is some chance that the converse might hold. A first indication of this is that the polynomials studied are characterized by their symmetries, which already tells you that the group action here is telling you more about these particular varieties than it would be for general $G$-varieties.

If the converse held, then one could in principle get a collapse of complexity classes by proving that there were no multiplicity obstructions. On the one hand, this seems quite hard. On the other hand, [Bürgisser-Ikenmeyer-Panova](https://doi.org/10.1090/jams/908) ([arXiv](https://arxiv.org/abs/1604.06431)) proved that there were no occurrence obstructions (multiplicty zero in one class and nonzero in the other).

However, even if the converse didn't hold, knowing that there were no multiplicity obstructions would still, I think, yield significant insight into the relationship between these problems. Each representation of $GL\_{n^2}$ appearing in the ring of (meta)polynomials (a polynomial ring in a number of variables that is equal to the number of monomials of degree $n$ in $n^2$ variables) corresponds to a $GL\_{n^2}$-invariant property of (ordinary) polynomials. The isomorphism type of such a representation tells you how its defining equations transform under the action of $GL\_{n^2}$. The multiplicity of a given isomorphism type (isotype) in the coordinate ring of one of these varieties $X$ thus tells you how many properties of that isotype the polynomials in $X$ have. Knowing that there were no multiplicity obstructions would still imply that these complexity classes share many more properties than one might initially think.


---

