4
$\begingroup$

$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?

$\endgroup$
3
  • $\begingroup$ There is an abusive moderator. $\endgroup$ – 1.. Feb 18 at 12:43
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Feb 19 at 4:18
  • $\begingroup$ 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. $\endgroup$ – Bjørn Kjos-Hanssen Feb 19 at 7:19
5
$\begingroup$

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 arXiv

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 (arXiv)

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 (arXiv) 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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.