More Like this

1. Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings

   Garg, A; Ikenmeyer, C; Makam, V; Oliveira, R; Walter, M; Wigderson, A (January 2020, Proceedings of the Computational Complexity Conference (CCC) 2020)

   We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of SLn(C)-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions). We develop a general framework, denoted algebraic circuit search problems, that captures many important problems in algebraic complexity and computational invariant theory. This framework encompasses various proof systems in proof complexity and some of the central problems in invariant theory as exposed by the Geometric Complexity Theory (GCT) program, including the aforementioned problem of computing succinct encodings for generators for invariant rings. 

   more » « less
2. Consistency of M-Theory on Non-Orientable Manifolds

   https://doi.org/10.1093/qmath/haab007  

   Freed, Daniel S; Hopkins, Michael J (April 2021, The Quarterly Journal of Mathematics)

   Abstract We prove that there is no parity anomaly in M-theory in the low-energy field theory approximation. Our approach is computational. We determine the generators for the 12-dimensional bordism group of pin manifolds with a w1-twisted integer lift of w4; these are the manifolds on which Wick-rotated M-theory exists. The anomaly cancellation comes down to computing a specific η-invariant and cubic form on these manifolds. Of interest beyond this specific problem are our expositions of computational techniques for η-invariants, the algebraic theory of cubic forms, Adams spectral sequence techniques and anomalies for spinor fields and Rarita–Schwinger fields. 

   more » « less
3. Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science

   https://doi.org/10.1016/j.difgeo.2022.101888  

   Landsberg, J.M. (April 2022, Differential geometry and its applications)

   Many fundamental questions in theoretical computer science are naturally expressed as special cases of the following problem: Let G be a complex reductive group, let V be a G-module, and let be elements of V. Determine if w is in the G-orbit closure of v. I explain the computer science problems, the questions in representation theory and algebraic geometry that they give rise to, and the new perspectives on old areas such as invariant theory that have arisen in light of these questions. I focus primarily on the complexity of matrix multiplication. 

   more » « less
4. Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties

   Makam, Visu; Wigderson, Avi (January 2020, FOCS 2020)

   null (Ed.)

   The object of study of this paper is the following multi-determinantal algebraic variety, SINGn, m, which captures the symbolic determinant identity testing (SDIT) problem (a canonical version of the polynomial identity testing (PIT) problem), and plays a central role in algebra, algebraic geometry and computational complexity theory. SINGn, m is the set of all m-tuples of n×n complex matrices which span only singular matrices. In other words, the determinant of any linear combination of the matrices in such a tuple vanishes. The algorithmic complexity of testing membership in SINGn, m is a central question in computational complexity. Having almost a trivial probabilistic algorithm, finding an efficient deterministic algorithm is a holy grail of derandomization, and to top it, will imply super-polynomial circuit lower bounds! A sequence of recent works suggests efficient deterministic “geodesic descent” algorithms for memberships in a general class of algebraic varieties, namely the null cones of (reductive) linear group actions. Can such algorithms be used for the problem above? Our main result is negative: SINGn, m is not the null cone of any such group action! This stands in stark contrast to a non-commutative analog of this variety (for which such algorithms work), and points to an inherent structural difficulty of SINGn, m. In other words, we provide a barrier for the attempts of derandomizing SDIT via these algorithms. To prove this result we identify precisely the group of symmetries of SINGn, m. We find this characterization, and the tools we introduce to prove it, of independent interest. Our characterization significantly generalizes a result of Frobenius for the special case m=1 (namely, computing the symmetries of the determinant). Our proof suggests a general method for determining the symmetries of general algebraic varieties, an algorithmic problem that was hardly studied and we believe is central to algebraic complexity. 

   more » « less
5. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights

   https://doi.org/10.1109/FOCS.2010.49  

   Cai, Jin-Yi; Chen, Xi. (January 2019, Computational complexity)

   The complexity of graph homomorphism problems has been the subject of intense study for some years. In this paper, we prove a decidable complexity dichotomy theorem for the partition function of directed graph homomorphisms. Our theorem applies to all non-negative weighted forms of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function ZA(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability on the other hand is algebraic and based on properties of polynomials. 

   more » « less