According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of linear polynomials. We prove the converse of Kumar's result and establish a tight connection between border Waring rank and the model of computation in Kumar's result. In this way, we obtain a new formulation of border Waring rank, up to a factor of the degree. We connect this new formulation to the orbit closure problem of the product-plus-power polynomial. We study this orbit closure from two directions: 1. We deborder this orbit closure and some related orbit closures, i.e., prove all points in the orbit closure have small non-border algebraic branching programs. 2. We fully implement the geometric complexity theory approach against the power sum by generalizing the ideas of Ikenmeyer-Kandasamy (STOC'20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that are constructed from just the symmetries of the polynomials.

In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. We use this to resolve an open question posed by Grochow, Kumar, Saks & Saraf (2017). Our result means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, it means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré-Birkhoff-Witt theorem for Lie algebras and on Gelfand-Tsetlin theory, for which we give the necessary comprehensive background.

A wide range of natural computational problems in computer science, mathematics, physics, and other sciences amounts to deciding if two objects are equivalent. Very often this equivalence is defined in terms of group actions. A natural question is to ask when two objects can be distinguished by polynomial functions that are invariant under the group action. For finite groups, this is just the usual notion of equivalence, but for continuous groups such as the general linear groups it gives rise to a new notion, called orbit closure intersection. This new notion has recently seen substantial interest in the community, as it captures, among others, the graph isomorphism problem, noncommutative polynomial identity testing, null cone problems in invariant theory, equivalence problems for tensor networks, and the classification of multiparty quantum states. Despite remarkable recent algorithmic progress in celebrated special cases, the computational complexity of general orbit closure intersection problems is currently quite unclear. In particular, tensors seem to give rise to the most difficult problems.In this work we start a systematic study of orbit closure intersection problems from the complexity-theoretic viewpoint. Our key contributions include:•We define a complexity class TOCI that captures the power of orbit closure intersection problems for general tensor actions.•We give an appropriate notion of algebraic reductions that imply polynomial-time reductions in the usual sense, but are amenable to invariant-theoretic techniques.•We identify several natural tensor problems that are complete for TOCI, one of which is the equivalence of PEPS tensor networks considered by Acuaviva et al (FOCS’23).•We show that the graph isomorphism problem can be reduced to these complete problems and hence $\mathbf{G I} \subseteq$ TOCI.As such, our work establishes the first lower bound on the computational complexity of orbit closure intersection problems, and it explains the difficulty of finding unconditional polynomialtime algorithms beyond special cases, as has been observed in the recent literature.

Tensors play a central role in various areas of computer science and mathematics, such as algebraic complexity theory (matrix multiplication), quantum information theory (entanglement), and additive combinatorics (slice rank). Fundamental problems about tensors are strongly tied to well-known questions in computational complexity - such as the problem of determining the matrix multiplication exponent via asymptotic rank, and the stronger Strassen asymptotic rank conjecture, which has recently been intimately linked to a whole range of computational problems. Unlike matrices, which are often well understood through their rank, tensors have such intricate structure that understanding them (and aforementioned problems) requires information of a more subtle nature. The moment polytope, going back decades to work in symplectic geometry, invariant theory, and representation theory, is a mathematical object associated to any tensor that collects such "rank-like"information. Their relevance has become apparent in several areas: (1) through applications in geometric complexity theory (GCT), (2) in the construction of functions in Strassen's asymptotic spectrum of tensors, (3) as entanglement polytopes in quantum information theory, and (4) in optimization via scaling algorithms. Despite their fundamental role and interest from many angles, little is known about these polytopes, and in particular for tensors beyondC2λ-λ.,⊗2λ-λ.,⊗2 andC2λ-λ.,⊗2λ-λ.,⊗2λ-λ.,⊗2 only sporadically have they been computed. Even less is known about the polytopes' inclusions and separations (which are particularly relevant for applications). We give a new algorithm for computing moment polytopes of tensors (and in fact moment polytopes for a natural general class of reductive algebraic groups) based on a mathematical characterization of moment polytopes by Franz. This algorithm enables us to compute moment polytopes of tensors of dimension an order of magnitude larger than previous methods, allowing us to compute with certainty, for the first time, all moment polytopes of tensors inC3λ-λ.,⊗3λ-λ.,⊗3, and with high probability those inC4λ-λ.,⊗4λ-λ.,⊗4. Towards an open problem in geometric complexity theory, we prove (guided by moment polytopes computed with our algorithm) separations between the moment polytopes of matrix multiplication tensors and unit tensors, showing in particular that the matrix multiplication moment polytopes are not maximal (i.e., not equal to the corresponding Kronecker polytopes). As a consequence of the above, we obtain a no-go result for a certain operational characterization of moment polytope inclusion, by proving that Strassen's asymptotic restriction on tensors does not imply moment polytope inclusion. Finally, based on our algorithmic observations, we construct explicit (concise) non-free tensors in every formatCn λ-Cn λ-Cn, thus solving a "hay in a haystack"problem for this generic property that plays an important role in Strassen's theory of asymptotic spectra.

Abstract We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give algorithms with complexity $$n^{p + 1}$$ n p + 1 for $$n \times n$$ n × n by $$n \times n^p$$ n × n p matrix multiplication. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $$\alpha$$ α via the big Coppersmith-Winograd tensors cannot exceed $$0.6218$$ 0.6218 .

We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the \emph{first} complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates.

Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known. In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5.

We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.

We consider the orbit closure containment problem, which, for a given vector and a group orbit, asks if the vector is contained in the closure of the group orbit. Recently, many algorithmic problems related to orbit closures have proved to be quite useful in giving polynomial time algorithms for special cases of the polynomial identity testing problem and several non-convex optimization problems. Answering a question posed by Wigderson, we show that the algorithmic problem corresponding to the orbit closure containment problem is NP-hard. We show this by establishing a computational equivalence between the solvability of homogeneous quadratic equations and a homogeneous version of the matrix completion problem, while showing that the latter is an instance of the orbit closure containment problem. Secondly, we consider the notion of slice rank of tensors, which was recently introduced by Tao, and has subsequently been used for breakthroughs in several combinatorial problems like capsets, sunflower free sets, tri-colored sum-free sets, and progression-free sets. We show that the corresponding algorithmic problem, which can also be phrased as a problem about union of orbit closures, is also NP-hard, hence answering an open question by Bürgisser, Garg, Oliveira, Walter, and Wigderson. We show this by using a connection between the slice rank and the size of a minimum vertex cover of a hypergraph revealed by Tao and Sawin.

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result, we establish the NP-completeness of several hazard detection problems.

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 653–664, 2017) and independently by Grochow, Kumar, Saks and Saraf (CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich’s famous barrier result (J. Comput. Syst. Sci., 55(1): 24–35, 1997) for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich’s barrier result relies on a widely believed assumption, namely, the existence of pseudo-random generators. Unfortunately, there is no known analogous theory of pseudo-randomness in the algebraic setting. Therefore, Forbes et al. use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al. are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions.

An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of n*n*n tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.