Questions tagged [gct]

Geometric Complexity Theory

Filter by
Sorted by
Tagged with
-5 votes
1 answer

Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$. Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$? Suppose if it turns out that $\...
  • 12.6k
2 votes
1 answer

Application of weak determinantal identities to GCT?

In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to ...
  • 12.6k
9 votes
1 answer

Noether’s Normalization Lemma for finite fields

My question is about theorems 4.1 and 4.2 in "Geometric Complexity Theory V". The first theorem states that there exists an EXPSPACE algorithm for constructing h.s.o.p. for $\Delta[\text{det},m]$ (...
6 votes
1 answer

Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

I was reading the GCT IV paper ( and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as ...
  • 269
2 votes
1 answer

Are there links between Geometry of Interaction and Geometric Complexity Theory?

I'm very much a novice in these subjects, but Geometry of Interaction and Geometric Complexity Theory seem to speak similar language and have vaguely similar goals. Am I not mistaken? Are there any ...
  • 457
45 votes
3 answers

Wikipedia-style explanation of Geometric Complexity Theory

Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment)...
18 votes
2 answers

Status on circuit lower bounds for polylog-bounded depth circuits

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
  • 279
39 votes
1 answer

Prerequisite for learning GCT

It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory. While I am a CS student and do NOT have classes of very abstract ...
  • 391
25 votes
3 answers

Constructivity in Natural Proof and Geometric Complexity

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$. Constructivity in Natural ...
  • 251
23 votes
4 answers

Papers on relation between computational complexity and algebraic geometry/topology?

I was wondering what papers I should read to understand this question A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of ...
8 votes
2 answers

Postselection in geometric complexity theory

Context: As I understand, in geometric complexity theory, the existence of obstructions serves as a proof-certificate, so to speak, for the nonexistence of an efficient computational circuit for the ...
1 vote
0 answers

From Determinant-Permanent to P-NP [duplicate]

Possible Duplicate: Does $VP \neq VNP$ imply $P \neq NP$? In his GCT papers Mulmuley first starts with the #P/NC question. And then gets into setting up a roadmap for how to show obstructions ( ...
  • 476
38 votes
2 answers

Mulmuley's GCT program

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
  • 4,001
6 votes
1 answer

The role of symmetry in geometric complexity theory?

I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $...
4 votes
0 answers

Is Witten's new method of quantization useful for geometric complexity theory? [closed]

The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
32 votes
2 answers

How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?

In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July. Several of the attendees argued that we should use GCT ...
38 votes
3 answers

Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
  • 383
22 votes
2 answers

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
  • 2,025