Abstract We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor $$T_{cw,q}$$ T c w , q is the square of its border rank for $$q > 2$$ q > 2 and that the border rank of its Kronecker cube is the cube of its border rank for $$q > 4$$ q > 4 . This answers questions raised implicitly by Coppersmith & Winograd (1990, §11) and explicitly by Bläser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith–Winograd tensor, $$T_{skewcw,q}$$ T s k e w c w , q . For $$q = 2$$ q = 2 , the Kronecker square of this tensor coincides with the $$3\times 3$$ 3 × 3 determinant polynomial, $$\det_{3} \in \mathbb{C}^{9} \otimes \mathbb{C}^{9} \otimes \mathbb{C}^{9}$$ det 3 ∈ C 9 ⊗ C 9 ⊗ C 9 , regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of $$\det_3$$ det 3 , exhibiting a strict submultiplicative behaviour for $$T_{skewcw,2}$$ T s k e w c w , 2 which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in $$\mathbb{C}^{3} \otimes \mathbb{C}^{3} \otimes \mathbb{C}^{3}$$ C 3 ⊗ C 3 ⊗ C 3 .

We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.

Grenet's determinantal representation for the permanent is optimal among determinantal representations that are equivariant with respect to left multiplication by permutation and diagonal matrices (roughly half the symmetry group of the permanent). In particular, if any optimal determinantal representation of the permanent must be polynomially related to one with such symmetry, then Valiant's conjecture on permanent v. determinant is true.

The rank of the matrix multiplication operator for ${\bf n}\times{\bf n}$ matrices is one of the most studied quantities in algebraic complexity theory. I prove that the rank is at least $3{\bf n}^2-o({\bf n}^2)$. More precisely, for any integer $p\leq {\bf n} -1$ the rank is at least $(3-\frac 1{p+1}){\bf n}^2-(1+2p\binom{2p}{p-1}){\bf n}$. The previous lower bound, due to Bläser, was $\frac 52{\bf n}^2-3{\bf n}$ (the case $p=1$). The new bounds improve Bläser's bound for all ${\bf n}>84$. I also prove lower bounds for rectangular matrices that are significantly better than the previous bound.

We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the geometric complexity theory program to prove a variant of Valiant's algebraic analogue of the $\mathbf{P}\neq\mathbf{NP}$ conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate.

In this paper, we consider the problem of space-time coding over Rician channels in the presence of spatio-temporal correlation. We derive an upper bound on the pairwise word error probability (PWEP) of space-time codes and use it as a basis for a unified approach to analysis and design of space-time codes over any flat, Rician or Rayleigh, block-fading channel. Based on the statistical properties of a Rician channel, the high-signal-to-noise ratio (SNR) behavior of the bound is either exponential or rational. In the former case, design criteria for space-time codes are based on a Euclidean-distance-like measure. However, in the latter case, design criteria are based on a rank criterion together with a coding gain criterion. The analysis of the bound shows that the performance of rank-deficient codes can be highly degraded in the presence of spatio-temporal correlation, but the performance degradation is not severe for full-rank codes. These codes exhibit robustness against the channel correlation profile. Specifically, for channels with a nonsingular covariance matrix, the asymptotic performance of a full-rank code is proportional to its performance in the independent and identically distributed (i.i.d.) case. In the case that the only constraint on the codewords is a maximum energy constraint, we show that the set of rank-deficient codes forms a proper algebraic subset of measure zero in the affine space of space-time codes. Thus, any randomly selected code is full rank with probability one. Hence, in this case, the main challenge in space-time coding is not maximizing diversity but optimizing coding gain. However, optimizing the coding gain is computationally hard and there exists no satisfactory algorithm to solve this problem in general. On the other hand, when we constrain codewords to be from a finite alphabet or to satisfy particular algebraic structures, e.g., group codes, lattice codes, or coset codes, the problem might be tractable, but rank-deficient codes might be highly probable at high spectral efficiency.