Geometric Complexity Theory

learn more… | top users | synonyms

28
votes
2answers
2k 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 ...
12
votes
2answers
471 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$ ...
30
votes
1answer
1k 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 ...
24
votes
3answers
619 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 ...
12
votes
2answers
895 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 ...
8
votes
2answers
355 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 ...
1
vote
0answers
142 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 ...
34
votes
2answers
1k 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 ...
5
votes
1answer
385 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: ...
4
votes
0answers
539 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 ...
28
votes
2answers
991 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 ...
22
votes
3answers
2k 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 ...
20
votes
2answers
978 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 ...