18
$\begingroup$

Geometric complexity theory has demonstrated that complexity theorists should care about algebraic geometry and representation theory, but, why should algebraic geometers and representation theorists care about geometric complexity theory?

More concretely: what does geometric complexity theory tell us about algebraic geometry and representation theory that is non-trivial?

Note: of course algebraic geometers and representation theorists qua mathematicians should care when their fields are applied to important issues in other fields (& they should even care about important issues in other fields that have no known connection to their fields!) ... I'm just asking specifically about the transit from computational complexity theory to algebraic geometry and representation theory because when there is a bridge it is natural to ask about information transit in both directions, and the direction addressed here has been addressed much less than the other direction.

$\endgroup$
1

1 Answer 1

9
$\begingroup$

(A caveat: GCT is intended to be a long program towards central conjectures in the field (like P vs NP), so one shouldn't necessarily expect "immediate returns" from it. In that regard, one may think of it perhaps analogous to the Langlands program.)

First, there are already results in GCT that say something about classical algebraic geometry and representation theory, independent of their applications to complexity. Some examples

  • Ikenmeyer, Mulmuley, and Walter showed that deciding positivity of Kronecker coefficients (tensor product coefficients for irreps of the symmetric group) is NP-hard. Assuming $\mathsf{P} \neq \mathsf{NP}$, this implies that there cannot be a saturated polyhedral interpretation of Kronecker coefficients the way there is for Littlewood-Richardson coefficients Knutson-Tao,(b/c a saturated polyhedral representation implies that deciding positivity is in $\mathsf{P}$, as was shown for LR coefficients).
  • Mulmuley, in "Geometric Complexity Theory V: efficient algorithms for Noether normalization" , showed that constructing generators for invariant rings of constant-rank reductive algebraic groups can be brought down to $\mathsf{DET} \subseteq \mathsf{P}$ (and quasi-poly time without the constraint on rank). This can be viewed as a final (essentially optimal, except for the constraint on rank) constructive version of a long series of results going back to Hilbert: Hilbert 1890 showed nonconstructively that these invariant rings were finitely generated, 1893 showed they could be constructed by an algorithm. Popov 1982 gave an explicit upper bound on the runtime, Derksen 2001 showed it could be done in $\mathsf{PSPACE}$, and finally Mulmuley's result.
  • Bürgisser, Ikenmeyer, and Panova showed that if the multiplicity of some irrep in the coordinate ring of the orbit closure of the determinant is zero, then it is also zero in the coordinate ring of the orbit closure of the (padded) permanent. This can be phrased as a result purely about representation theory of general linear groups, but whose proof combines representation-theoretic results with reductions from complexity theory in a crucial way.

Second, more generally, one of the things that has been realized by the community over the last couple of decades is that many classical objects studied in algebraic geometry are the same objects being studied by different names in (algebraic/geometric) complexity theory. In other words, algebraic geometers (may) already care about these things, and so should care about GCT just in the sense of finding another community working on the same topics. For example:

  • Secant varieties of Segre embedding? Very classical. Also the same as the algebraic complexity of tensors, in particular the matrix multiplication tensor, a central question in complexity.
  • Secant varieties of Chow varieties (products of linear forms) are the same as the class of functions computable by depth 3 algebraic circuits (standard fare in complexity theory)
  • Secant varieties of Veronese embeddings are the class of functions computable by depth 3 powering circuits.
  • "Determinantal representations of polynomials" is the same as determinantal complexity, which arises in Valiant's algebraic analogue of P vs NP (known as the permanent vs determinant conjecture)
  • Trace polynomials and invariants of quivers are the same as algebraic branching programs in complexity (and the same as matrix product states in quantum physics)
  • Singular matrix spaces are closely connected to the "Symbolic Determinant Identity Testing" problem, a key problem in complexity theory (whose derandomization was shown equivalent to derandomizing/giving efficiently constructive versions of Noether normalization in GCT V, ibid)

Details of many of these can be found in Landsberg's book "Geometry & Complexity Theory" and survey, "GCT: An introduction for geometers"

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .