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. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture

   https://doi.org/10.4230/lipics.ccc.2024.14  

   Bürgisser, Peter; Doğan, Mahmut Levent; Makam, Visu; Walter, Michael; Wigderson, Avi (July 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous questions and structures in physics, mathematics, computer science, optimization, and more. Accordingly, it is of high interest to understand their computational complexity. Recently, Bürgisser et al. (2021) gave the first polynomial-time algorithms for orbit problems of torus actions, that is, actions of commutative continuous groups on Euclidean space. In this work, motivated by theoretical and practical applications, we study the computational complexity of robust generalizations of these orbit problems, which amount to approximating the distance of orbits in ℂⁿ up to a factor γ ≥ 1. In particular, this allows deciding whether two inputs are approximately in the same orbit or far from being so. On the one hand, we prove the NP-hardness of this problem for γ = n^Ω(1/log log n) by reducing the closest vector problem for lattices to it. On the other hand, we describe algorithms for solving this problem for an approximation factor γ = exp(poly(n)). Our algorithms combine tools from invariant theory and algorithmic lattice theory, and they also provide group elements witnessing the proximity of the given orbits (in contrast to the algebraic algorithms of prior work). We prove that they run in polynomial time if and only if a version of the famous number-theoretic abc-conjecture holds - establishing a new and surprising connection between computational complexity and number theory. 

   more » « less
5. 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