Questions tagged [gct]
Geometric Complexity Theory
18
questions
-5
votes
1
answer
217
views
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
156
views
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
363
views
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]$ (...
- 1,859
6
votes
1
answer
273
views
Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory
I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) 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
228
views
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
5k
views
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)...
- 3,920
18
votes
2
answers
1k
views
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
3k
views
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
944
views
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
3k
views
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 ...
- 1,631
8
votes
2
answers
432
views
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 ...
- 185
1
vote
0
answers
174
views
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
3k
views
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
525
views
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: $...
- 20.7k
4
votes
0
answers
714
views
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 ...
- 149
32
votes
2
answers
2k
views
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 ...
- 1,278
38
votes
3
answers
4k
views
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
1k
views
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