Kronecker Scaling of Tensors with Applications to Arithmetic Circuits and Algorithms

In this paper, we expand the reach of Strassen’s trilinear theory to sequences of three-tensors

that are not Kronecker powers (1), but have a Kronecker scaling property of “approximate” smoothness in the following precise sense:

For all $\delta >0$, there exist infinitely many $d=1,2,\mathrm{\dots }$ such that for all large enough $n=1,2,\mathrm{\dots }$ the tensor $T_n$ is a sum of at most $2^{\delta n}$ tensors, each of which is a restriction of $T_d^{\otimes s}$ for $s\le (1+\delta )n/d$.

It is immediate that a Kronecker power sequence (1) has the Kronecker scaling property. What is considerably less immediate – and our main result in this paper – is that the sequence of balanced tripartitioning tensors has this property. In what follows we view three-tensors as set-multilinear polynomials in three sets of indeterminates $x,y,z$ and write $[k]=\{1,2,\mathrm{\dots },k\}$.

Combined with the fact that the decomposition underlying Theorem 1.1 is efficiently computable in a sense to be made precise later, and using well-known techniques in Strassen’s trilinear theory, our main result has the following corollary in terms of uniform arithmetic circuits:

Theorem 1.2 highlights the significance of the exponential rate of growth ${\mathrm{\Lambda }}^d$ of the tensor rank $𝐑(P_d)$ along the sequence (3) as $d$ grows. It will be convenient to study such growth rates via exponents of three-tensor sequences as recently studied in [28]; for a sequence $T_{\mathbb{N}}$ consisting of three-tensors $T_n$ of shape $s_n\times s_n\times s_n$ for $n\in \mathbb{N}$, define the exponent

We stress that the quantity of interest is the tensor rank, not the asymptotic rank, along the sequence (3). Later in Theorem 3.3 we will, however, show that it is a nontrivial consequence of the Kronecker scaling property and our main theorem (Theorem 1.1 and its explicit-decomposition version, Theorem 3.2) that the rank and asymptotic rank have identical exponents along the sequence.

When $S$ is an individual tensor of shape $d\times d\times d$, we write $\sigma (S)$ for the exponent of the Kronecker power sequence (1); the exponent $\sigma (S)$ and the asymptotic rank $\underset{\sim }{𝐑}(S)$ are related by $\underset{\sim }{𝐑}(S)=d^{\sigma (S)}$. The exponent (4) has the convenience that it abstracts away the shape of the underlying tensors and thus enables more concise complexity characterizations. For example, using exponents, Strassen’s characterization [47] of the exponent $\omega$ of square matrix multiplication becomes $\omega =2\sigma ({\mathrm{MM}}_2)$.

Analogously to the matrix multiplication exponent $\omega$, in the language of exponents, our applications presented in the next subsection motivate the following question concerning the sequence $P_{\mathbb{N}}$ consisting of the balanced tripartitioning tensors (3):

What is the value of the exponent $\sigma (P_{\mathbb{N}})$ of balanced tripartitioning?

We know that the exponent $\sigma (P_{\mathbb{N}})$ satisfies $1\le \sigma (P_{\mathbb{N}})\le H{(1/3)}^{-1}\le 1.0891$, where $H(\lambda )=-\lambda {\log }_2\lambda -(1-\lambda ){\log }_2(1-\lambda )$ is the binary entropy function.²²2Indeed, here the lower bound follows from matrix rank by a standard flattening argument for the tensor $P_n$, and the upper bound is a consequence of Stirling’s formula (e.g. [42]) and the fact that $P_n$ is a restriction of shape $\left(\genfrac{}{}{0pt}{}{3n}{n}\right)\times \left(\genfrac{}{}{0pt}{}{3n}{n}\right)\times \left(\genfrac{}{}{0pt}{}{3n}{n}\right)$ of the $(3n)$^th Kronecker power of a tensor of shape $2\times 2\times 2$, where all the latter tensors are known to have border rank at most $2$ (e.g. [34]). As our applications will motivate, it would be of interest to know already whether . As we will discuss after our applications, bold conjectures in Strassen’s trilinear theory – Strassen’s so-called asymptotic rank conjecture [49, Conjecture 5.3] (see also [12, Problem 15.5], [15, Conjecture 1.4], and [55, Section 13, p. 122]) in particular – imply an affirmative answer and in fact the conclusion $\sigma (P_{\mathbb{N}})=1$.

We are now ready for our applications in arithmetic circuits and algorithms. All these applications of our main theorem are rather direct or follow earlier work, and hence are not our main contribution.

In the language of tensor exponents, Strassen conjectured [49, Conjecture 5.3] that the exponent $\sigma (S)=1$ for all tensors $S$ that are tight and concise and have shape $d\times d\times d$ for some $d=1,2,\mathrm{\dots }$. The conjecture is known to be true for $d=1,2$ but remains open for $d\ge 3$; already the first open case $d=3$ is of considerable interest since a proof for $d=3$ would imply $\omega =2$ by an application of the Coppersmith–Winograd method [16] to a particular tensor. The balanced tripartitioning tensors $P_n$ are known to be both tight and concise, which via the asymptotic scaling identity (cf. Theorem 3.3) immediately translates to $\sigma (P_{\mathbb{N}})=1$. Thus, under Strassen’s asymptotic rank conjecture, Theorem 1.3 yields uniform arithmetic circuits for the permanent that are exponentially smaller than Ryser’s formula. Also stronger versions of the conjecture without the tightness and conciseness assumptions appear in the literature (e.g. [12, Problem 15.5], [15, Conjecture 1.4], and [55, Section 13, p. 122]).

Among the present main evidence towards the conjecture is Strassen’s result [47] (see also [13, 14]) that $\sigma (S)\le 2\omega /3=\frac{4}{3}\sigma ({\mathrm{MM}}_2)$ for any tensor $S$ of shape $d\times d\times d$ for $d=1,2,\mathrm{\dots }$. It is also known that there are explicit sequences of tensors whose exponent conjecture-agnostically captures the worst-case tensor exponent $\sigma (d)={sup}_S\sigma (S)$, where $S$ ranges over $d\times d\times d$ tensors [28].

In motivating the present paper, we prefer a similar, agnostic, view to the asymptotic rank conjecture, and would rather like to highlight the analysis of the balanced tripartitioning sequence $P_{\mathbb{N}}$ and its exponent $\sigma (P_{\mathbb{N}})$ as a natural object for further study. Indeed, each tensor $P_n(x,y,z)$ is invariant under the symmetric group $S_{3n}$ acting on $\left(\genfrac{}{}{0pt}{}{[3n]}{n}\right)$ and the sets of indeterminates $x,y,z$ diagonally, suggesting potential for study with techniques from representation theory. On the one hand, a proof that would via Theorem 1.3 give a considerable advance in the study of the permanent, where progress has yielded only subexponential speedup since Ryser’s 1963 formula. On the other hand, a proof that $\sigma (P_{\mathbb{N}})>1$ would disprove the asymptotic rank conjecture. Theorem 1.3 also implies that strong exponential lower bounds for the arithmetic complexity of the permanent disprove the asymptotic rank conjecture.

Let us now give a brief description of our main theorem (Theorem 1.1) and its explicit-decomposition version (Theorem 3.2 in what follows). For brevity let $U=[3n]$. The key idea to decompose $P_n$ into a sum of restrictions of $P_d^{\otimes s}$ is to assign an intersection type, or, briefly, type, $\tau$ to each tripartition $A\cup B\cup C=U$ with $|A|=|B|=|C|=n$. Suppose that $n=br$ and $r=gs$ for positive integers $b,g,s$. Fix a partition $U=U_1\cup U_2\cup \mathrm{\cdots }\cup U_r$ into sets $U_i$ with $|U_i|=3b$ for $i\in [r]$. The type $\tau =(\alpha ,\beta ,\gamma )$ of a tripartition $(A,B,C)$ now consists of three $r$-dimensional vectors $\alpha ,\beta ,\gamma \in {\{0,1,\mathrm{\dots },3b\}}^r$ with ${\alpha }_i=|A\cap U_i|$, ${\beta }_i=|B\cap U_i|$, and ${\gamma }_i=|C\cap U_i|$ for all $i\in [r]$. Clearly ${\alpha }_i+{\beta }_i+{\gamma }_i=3b$ for all $i\in [r]$ as well as ${\sum }_{i\in [r]}{\alpha }_i=n$, ${\sum }_{i\in [r]}{\beta }_i=n$, and ${\sum }_{i\in [r]}{\gamma }_i=n$. Let us write $T_b^r$ for the set of all types. For a type $\tau \in T_b^r$, let us write ${𝒫}^{\tau }$ for the set of all tripartitions $(A,B,C)$ of $U$ of type $\tau$. Since every tripartition has a unique type, we clearly have that the tensors $P_n^{\tau }=P_n^{\tau }(x,y,z)={\sum }_{(A,B,C)\in {𝒫}^{\tau }}{x}_A{y}_B{z}_C$ for $\tau \in T_b^r$ decompose $P_n$ into the sum $P_n={\sum }_{\tau \in T_b^r}{P}_n^{\tau }$. For any $\delta >0$, we can find $b$ large enough so that $|T_b^r|\le 2^{\delta n}$, so all we need to do is to show that each $P_n^{\tau }$ regardless of the $\tau$ can be obtained as a restriction of $P_d^{\otimes s}$ with $s\le (1+\delta )n/d$. We will show this for $d=b(g+36)$ when $g$ is a large enough constant depending on $\delta$. Given a type $\tau \in T_b^r$ as input, the key algorithmic idea is to efficiently compute a partition of $[r]$ into $G_1^{\tau }\cup G_2^{\tau }\cup \mathrm{\cdots }\cup G_s^{\tau }$ with $|G_1^{\tau }|=|G_2^{\tau }|=\mathrm{\cdots }=|G_s^{\tau }|=g$ that is balanced, i.e.,

This balance property and its efficient computability is crucial in embedding $P_n^{\tau }$ into a restriction of $P_d^{\otimes s}$ for $d=b(g+36)$. We show that the balanced partition $[r]=G_1^{\tau }\cup G_2^{\tau }\cup \mathrm{\cdots }\cup G_s^{\tau }$ exists and can be computed by dynamic programming efficiently enough via a concentration version (Lemma 3.1) of the classical Steinitz lemma (Lemma 2.2); the latter shows that a sum of vectors of bounded norm in a Euclidean space can be permuted so that all the prefix sums adjusted for size closely track the full sum; cf. (5). We call this technique Steinitz balancing. Once each decomposition of $P_n^{\tau }$ as a restriction of $P_d^{\otimes s}$ is available, our main circuit construction (Theorem 1.2) is essentially a consequence of a standard circuit version of Yates’s algorithm for evaluating Kronecker powers (cf. Lemma 4.1).

Kaski and Michałek [28] study tensor sequences that are universal in the sense that their exponents capture the worst-case exponent $\sigma (d)$ for $d\times d\times d$ tensors. Tripartitioning tensors appear in earlier works of Björklund and Kaski [7] and Pratt [40]; both works rely on randomization to decide the existence of a tripartition and essentially do not have the arithmetic and counting properties enabled by our present Kronecker scaling decomposition and the Steinitz balancing technique. Pratt also observes the upper bound $𝐑(P_n)\le 2^{3n-1}$ over any field $𝔽$ with $\mathrm{char}𝔽\ne 2$. Björklund, Curticapean, Husfeldt, Kaski, and Pratt [4] derandomize the randomized construction to a deterministic one, and extend the construction to unbalanced tripartitioning.

The rest of this paper is organized as follows. Section 2 reviews our definitions, notation, and background results. Section 3 proves our main results on Kronecker scaling of balanced tripartitioning tensors. Section 4 develops the consequent uniform circuit constructions for evaluating balanced tripartitioning polynomials. Section 5 proves our applications to counting problems, including the permanent in particular. The full version contains the proofs of our applications to parameterized problems and to Hamiltonicity parameterized by treewidth, including the Kronecker scaling property for the matchings connectivity tensors.

We work in coordinates and represent tensors as multilinear polynomials with the following conventions. All of our tensors have order three unless otherwise mentioned. Let $𝔽$ be a field and let $U$ be a finite set. Let $x,y,z$ be three sets of polynomial indeterminates indexed by the subsets of $U$. A tensor $S\in 𝔽[x,y,z]$ is a multilinear polynomial of the form

with coefficients $s_{ABC}\in 𝔽$. We say that $S$ is indexed by $U$ and that $S$ has shape $p\times q\times r$ for $p=|\{A\subseteq U:s_{ABC}\ne 0\text{ for some }B,C\subseteq U\}|$, $q=|\{B\subseteq U:s_{ABC}\ne 0\text{ for some }A,C\subseteq U\}|$, and $r=|\{C\subseteq U:s_{ABC}\ne 0\text{ for some }A,B\subseteq U\}|$.

Let $x$ be a set of indeterminates and let $𝔽$ be a field. An arithmetic circuit over $𝔽$ (with variables in $x$) is a directed acyclic graph (DAG) defined as follows. The indegree-zero nodes of the graph are labeled either by a variable from $x$ or by a constant in $𝔽$. Each internal node $v$ is labeled by either $+$ or $\times$, and it has one or more children nodes computing polynomials $P_1,P_2,\mathrm{\dots },P_r$, with arcs leading from these children into $v$. The node $v$ computes $P_1+P_2+\mathrm{\cdots }+P_r$ (in the case of $+$) or $P_1\cdot P_2\cdot \mathrm{\cdots }\cdot P_r$ (in the case of $\times$). Finally, one or more designated nodes with outdegree zero serve as the output(s) of the circuit. The size of a circuit is the number of arcs it contains.⁷⁷7Although the standard measure of an arithmetic circuit’s size is the number of gates, we will use the number of arcs instead since it directly corresponds to the number of arithmetic operations required to evaluate the circuit.

We say that an arithmetic circuit is homogeneous if the polynomial computed at every internal node is homogeneous. It is possible to transform a nonhomogeneous arithmetic circuit into a homogeneous one.

A circuit is called skew if every multiplication gate has exactly two children and one of these children is an input gate. More generally, for a constant $q\in \mathbb{N}$, we say that a circuit is $q$-skew if every multiplication gate has exactly two children and at least one of these is computed by a subcircuit that produces a polynomial of degree at most $q$. Note that the homogenization described in Lemma 2.1 preserves the $q$-skew property.

The following sharp version of Steinitz’s [45] lemma was proved by Grinberg and Sevast′janov [26].

We observe that a permutation $\pi$ that minimizes the maximum of the left-hand side of (5) over all $k\in [r]$ with respect to the infinity (maximum absolute value coordinate) norm can be found in time polynomial in $r$ by dynamic programming when each vector in the input $u_1,u_2,\mathrm{\dots },u_r$ is drawn from a set $S\subseteq {ℝ}^d$ of vectors with $|S|=O(1)$, $d=O(1)$, and each vector in $S$ has $O(1)$-bit rational coordinates; this will be the case in our applications in what follows. Indeed, with at most $|S|$ distinct vectors in the input, there are at most $\left(\genfrac{}{}{0pt}{}{r+|S|-1}{|S|-1}\right)$ distinct inputs when we view the input as a multiset of $r$ vectors. We can now use dynamic programming on the input multiset as follows. For each sub-multiset of size $1\le m\le r$ and each selection of the $m$^th summand in the sub-multiset, we tabulate the optimum min-max value, with the maximum taken over $k\in [m]$. In particular, we will tabulate at most ${\sum }_{m=1}^r\left(\genfrac{}{}{0pt}{}{m+|S|-1}{|S|-1}\right)|S|\le r^{O(1)}$ values. By tracing the table back one summand at a time, we find an optimum permutation.

We start with a simple corollary enabled by Lemma 2.2 which shows that one can partition a sum with bounded summands into parts such that the average of each part concentrates around the global average.

We are now ready for our main theorem that establishes the Kronecker scaling property for balanced tripartitioning tensors. Let $b,g,s$ be positive integers and let $q=br$ and $r=gs$. Let $U$ be a $3q$-element set. We show how to partition the tensor $P_q=P_q[U]$ into disjoint components such that each component is a restriction of the $s$^th Kronecker power of $P_{b(g+36)}$. Crucially, we rely on the Steinitz concentration lemma (Lemma 3.1) to construct the partition into balanced sets in each component – we call this technique Steinitz balancing.

Partition the set $U$ arbitrarily into $r$ sets $U_1,U_2,\mathrm{\dots },U_r$ of size $3b$ each. Let $\alpha ,\beta ,\gamma \in {\{0,1,\mathrm{\dots },3b\}}^r$ with

and ${\alpha }_i+{\beta }_i+{\gamma }_i=3b$ for all $i\in [r]$. We say that the three-tuple $\tau =(\alpha ,\beta ,\gamma )$ is an intersection type, or type for short. Let us write $T_b^r$ for the set of all intersection types. Each balanced tripartition $A\cup B\cup C=U$ with $A,B,C\in \left(\genfrac{}{}{0pt}{}{U}{q}\right)$ now defines a unique type $\tau =(\alpha ,\beta ,\gamma )$ by ${\alpha }_i=|A\cap U_i|$, ${\beta }_i=|B\cap U_i|$, and ${\gamma }_i=|C\cap U_i|$ for all $i\in [r]$. The types $\tau$ will index the disjoint components in our decomposition of $P_q[U]$.

We now proceed with Steinitz balancing. Fix a type $\tau =(\alpha ,\beta ,\gamma )\in T_b^r$. In the Steinitz concentration lemma (Lemma 3.1), take $d=3$, the infinity (maximum absolute value coordinate) norm, $g_1=g_2=\mathrm{\cdots }=g_s=g$, and $v_i=\frac{1}{3b}({\alpha }_i,{\beta }_i,{\gamma }_i)$ for all $i\in [r]$ and use (7) to obtain a set partition $G_1^{\tau }\cup G_2^{\tau }\cup \mathrm{\cdots }\cup G_s^{\tau }=[r]$ such that for all $j\in [s]$ we have

For each $j\in [s]$, introduce a $108b$-element set $V_j$ and observe from ${\alpha }_i+{\beta }_i+{\gamma }_i=3b$ and (8) that we can fix an arbitrary set partition $V_j^{\alpha }\cup V_j^{\beta }\cup V_j^{\gamma }=V_j$ with

We assume that the sets $U,V_1,V_2,\mathrm{\dots },V_s$ are pairwise disjoint. For each $j\in [s]$, define ${\overline{U}}_j^{\tau }=({\cup }_{i\in G_j^{\tau }}{U}_i)\cup V_j$. Define $\overline{U}={\cup }_{j\in [s]}{\overline{U}}_j^{\tau }=U\cup V_1\cup V_2\cup \mathrm{\cdots }\cup V_s$. For all $\overline{A},\overline{B},\overline{C}\subseteq \overline{U}$, define the three restrictions

We are now ready for the main Kronecker scaling theorem.

Let us now derive an asymptotic consequence of Theorem 3.2. We abbreviate $P_n$ for the tensor $P_n[U]$ with $U=[3n]$. We also recall from Section 1 that we write $\sigma (P_{\mathbb{N}})$ for the exponent (4) of balanced tripartitioning (3).