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. 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 $\mathbb{C}^n$ 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(\mathrm{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.

Tensor networks have a gauge degree of freedom on the virtual degrees of freedom that are contracted. A canonical form is a choice of fixing this degree of freedom. For matrix product states, choosing a canonical form is a powerful tool, both for theoretical and numerical purposes. On the other hand, for tensor networks in dimension two or greater there is only limited understanding of the gauge symmetry. Here we introduce a new canonical form, the minimal canonical form, which applies to projected entangled pair states (PEPS) in any dimension, and prove a corresponding fundamental theorem. Already for matrix product states this gives a new canonical form, while in higher dimensions it is the first rigorous definition of a canonical form valid for any choice of tensor. We show that two tensors have the same minimal canonical forms if and only if they are gauge equivalent up to taking limits; moreover, this is the case if and only if they give the same quantum state for any geometry. In particular, this implies that the latter problem is decidable – in contrast to the well-known undecidability for equality of PEPS on grids. We also provide rigorous algorithms for computing minimal canonical forms. To achieve this we draw on geometric invariant theory and recent progress in theoretical computer science in non-commutative group optimization.

In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.

Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction). In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V ) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3+o(1} . Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k−1}). Moreover, as an application we prove that the subrank is not additive under the direct sum. The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers–Wolf, 2011; Lovett, 2018; Bhrushundi–Harsha–Hatami–Kopparty–Kumar, 2020), geometric rank (Kopparty–Moshkovitz–Zuiddam, 2020), and G-stable rank (Derksen, 2020). Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.

An$(m,n,a,b)$-tensor code consists of$m\times n$matrices whose columns satisfy ‘$a$’ parity checks and rows satisfy ‘$b$’ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when$a=1$, i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes ($\mathrm {MDS}(\ell)$codes) which is an interesting generalization of the well-known MDS codes, where$\ell $captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with$a=1$is MR if the row code is an$\mathrm {MDS}(m)$code. We then show that$\mathrm {MDS}(m)$codes satisfy some weak duality. Using this characterization and duality, we prove that$(m,n,a=1,b)$-MR tensor codes require fields of size$q=\Omega _{m,b}(n^{\min \{b,m\}-1})$. Our lower bound also extends to the setting of$a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when$a=1$).

An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure containment. These capture and relate to a variety of problems within mathematics, physics and computer science, optimization and statistics. These orbit problems extend the more basic null cone problem, whose algorithmic complexity has seen significant progress in recent years. In this paper, we initiate a study of these problems by focusing on the actions of commutative groups (namely, tori). We explain how this setting is motivated from questions in algebraic complexity, and is still rich enough to capture interesting combinatorial algorithmic problems. While the structural theory of commutative actions is well understood, no general efficient algorithms were known for the aforementioned problems. Our main results are polynomial time algorithms for all three problems. We also show how to efficiently find separating invariants for orbits, and how to compute systems of generating rational invariants for these actions (in contrast, for polynomial invariants the latter is known to be hard). Our techniques are based on a combination of fundamental results in invariant theory, linear programming, and algorithmic lattice theory.

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 SL_n(ℂ)-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.

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.

We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on $k$-tensors cannot yield non-trivial lower bounds on the rank of $d$-tensors, for any constant $d>k$. This significantly extends recent barrier results on the limits of (matrix) rank methods by Efremenko, Garg, Oliveira and Wigderson, which handles the (very important) case $k=2$. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic $k$-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for $k=2$. To prove an analogous statement for $k>2$ we develop a "numeric to symbolic" transfer of algebraic relations to algebraic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP $\neq$ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds.