Faster Algorithms for Rectangular Matrix Multiplication

Introduction

Finding the optimal value of the exponent of square matrix multiplication is naturally one of the most important open problems in algebraic complexity. It is widely believed that the product of two $n\times n$ matrices can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any constant $\epsilon>0$. Several conjectures, including conjectures about combinatorial structures and about group theory , would, if true, lead to this result (see also for recent work on these conjectures). Another way to interpret this open problem is by considering the multiplication of an $n\times m$ matrix by an $m\times n$ matrix. Suppose that the matrices are defined over a field. For any $k>0$, define the exponent of such a rectangular matrix multiplication as follows:

where $C(n,n,\lfloor n^{k}\rfloor)$ denotes the minimum number of arithmetic operations needed to multiply an $n\times\lfloor n^{k}\rfloor$ matrix by an $\lfloor n^{k}\rfloor\times n$ matrix. Note that, while the value $\omega(1,1,k)$ may depend on the field under consideration, it is known that it can depend only on the characteristic of the field . Define $\omega=\omega(1,1,1)$ and $\alpha=\sup\{k\>|\>\omega(1,1,k)=2\}$. The value $\omega$ represents the exponent of square matrix multiplication, and the value $\alpha$ essentially represents the largest value such that the product of an $n\times n^{\alpha}$ matrix by an $n^{\alpha}\times n$ matrix can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any constant $\epsilon$. Since $\omega=2$ if and only if $\alpha=1$, one possible strategy towards showing that $\omega=2$ is to give lower bounds on $\alpha$. Coppersmith showed in 1982 that $\alpha>0.172$. Then, based on the techniques developed in , Coppersmith improved this lower bound to $\alpha>0.29462$. This is the best lower bound on $\alpha$ known so far.

Excepting Coppersmith’s works on the value $\alpha$, there have been relatively few algorithms that focused specifically on rectangular matrix multiplication. Since it is well known (see, e.g, ) that multiplying an $n\times n$ matrix by an $n\times m$ matrix, or an $m\times n$ matrix by an $n\times n$ matrix, can be done with the same number of arithmetic operations as multiplying an $n\times m$ matrix by an $m\times n$ matrix, the value $\omega(1,1,k)$ represents the exponent of all these three types of rectangular matrix multiplications. Note that, by decomposing the product into smaller matrix products, it is easy to obtain (see, e.g, ) the following upper bound:

Lotti and Romani obtained nontrivial upper bounds on $\omega(1,1,k)$ based on the seminal result by Coppersmith and on early works on square matrix multiplication. Huang and Pan showed how to apply ideas from to the rectangular setting and obtained the upper bound $\omega(1,1,2)<3.333954$, but this approach did not lead to any upper bound better than (1) for $k\leq 1$. Ke, Zeng, Han and Pan further improved Huang and Pan’s result to $\omega(1,1,2)<3.2699$, by using again the approach from , and also reported the upper bounds $\omega(1,1,0.8)<2.2356$ and $\omega(1,1,0.5356)<2.0712$, which are better than those obtained by (1). Their approach, nevertheless, did not give any improvement for the value of $\alpha$.

Besides the fact that a better understanding of $\omega(1,1,k)$ gives insights into the nature of matrix multiplication and ultimately may help showing that $\omega=2$, fast algorithms for multiplying an $n\times n^{k}$ matrix by an $n^{k}\times n$ with $k\neq 1$ have also a multitude of applications. Typical examples not directly related to linear algebra include the construction of fast algorithms for the all-pairs shortest paths problem , the dynamic computation of the transitive closure , finding ancestors , detecting directed cycles , or computing the diameter of a graph . Rectangular matrix multiplication has also been used in computational complexity , and to speed-up sparse square matrix multiplication or tasks in computational geometry . Obtaining new upper bounds on $\omega(1,1,k)$ would thus reduce the asymptotic time complexity of algorithms in a wide range of areas. We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical.

Short description of the approach by Coppersmith and Winograd.

In view of the last result, it was natural to ask if taking larger tensor powers of $F_{q}$ as the basic construction leads to better bounds on $\omega$. The case $r=3$ was explicitly mentioned as an open problem in but did not seem to lead to any improvement. Stothers and Vassilevska Williams succeeded in analyzing the fourth tensor product $F_{q}^{\otimes 4}$ and obtained a better upper bound on $\omega$, the first improvement in more that twenty years. Vassilevska Williams further presented a general framework that enables a systematic analysis for higher tensor products of the basis construction, and used this framework to show that $\omega<2.3727$, for the basic construction $F^{\otimes 8}$, the best upper bound obtained so far.

The algorithms for rectangular matrix multiplication already mentioned use a similar approach. Huang and Pan obtained their improvement on $\omega(1,1,2)$ by taking the easiest of the three construction in and carefully modifying the analysis to evaluate the complexity of rectangular matrix multiplication. Ke, Zeng, Han and Pan obtained their improvements similarly, but by using the second basic construction from (the construction $F_{q}$) instead, which lead to better upper bounds. These approaches, while very natural, do not provide any nontrivial lower bounds on $\alpha$: the upper bounds on $\omega(1,1,k)$ obtained are strictly larger than 2 even for small values of $k$. In order to obtain the lower bound $\alpha>0.29462$, Coppersmith relied on a more complex approach: the basic construction considered is still $F_{q}$, but several instances for distinct values of $q$ are combined together in a subtle way in order to keep the complexity of the resulting algorithm small enough (i.e., not larger than $n^{2+o(1)}$).

Statement of our results and discussion.

In this paper we construct new algorithms for rectangular matrix multiplication, by taking the tensor power $F_{q}\otimes F_{q}$ as basic construction and analyzing this construction in the framework of rectangular matrix multiplication. We use these ideas to prove that $\omega(1,1,k)=2$ for any $k\leq 0.3029805$, as stated in the following theorem.

For any value $k<0.3029805...$, the product of an $n\times n^{k}$ matrix by an $n^{k}\times n$ matrix can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any constant $\epsilon>0$.

Theorem 1.1 shows that $\alpha>0.30298$, which improves the previous record $\alpha>0.29462$ by Coppersmith. More generally, in the present work we present an algorithm for multiplying an $n\times n^{k}$ matrix by an $n^{k}\times n$ matrix, for any value $k$. We show that the complexity of this algorithm can be expressed as a (nonlinear) optimization problem, and use this formulation to derive upper bounds on $\omega(1,1,k)$. Table 1 shows the bounds we obtain for several values of $k$. The bounds obtained for $0\leq k\leq 1$ are represented in Figure 1 as well.

The results of this paper can be seen as a generalization of Coppersmith-Winograd’s approach to the rectangular setting. In the case of square matrix multiplication (i.e., for $k=1$), we recover naturally the same upper bound $\omega(1,1,1)<2.375477$ as the one obtained in . Let us mention that we can, in a rather straightforward way, combine our results with the upper bound $\omega<2.3727$ by Vassilevska Williams to obtain slightly improved bounds for $k\approx 1$. The idea is, very similarly to how Equation (1) was obtained, to exploit the convexity of the function $\omega(1,1,k)$. Concretely, for any fixed value $0\leq k_{0}<1$, the inequality

holds for any $k$ such that $k_{0}\leq k\leq 1$. This enables us to combine an upper bound on $\omega(1,1,k_{0})$, for instance one of the values in Table 1, with the improved upper bound $\omega<2.3727$ by Vassilevska Williams. Since the improvement is small and concerns only the case $k\approx 1$, we will not discuss it further.

For $k>0.29462$ and $k\neq 1$, the complexity of our algorithms is better than all known algorithms for rectangular matrix multiplication, including the algorithms mentioned above. Moreover, for $0.30298<k<1$, our new bounds are significantly better than what can be obtained solely from the bound $\alpha>0.30298$ and $\omega<2.375477$ through Equation (1), as illustrated in Figure 1. This suggests that non-negligible improvements can be obtained for all applications of rectangular matrix multiplications that rely on this simple linear interpolation — we will elaborate on this subject in Subsection 1.1.

Let us compare more precisely our results with those reported in . For $k=2$, we obtain $\omega(1,1,2)<3.256689$ while Ke et al. obtained $\omega(1,1,2)<3.2699$ by using the basic construction $F_{q}$. Our improvements are of the same order for the other two values ($k=0.8$ and $k=0.5356$) analyzed in , as can be seen from Table 1. Note that the order of magnitude of the improvements here is similar to what was obtained in by changing the basic construction from $F_{q}$ to $F_{q}\otimes F_{q}$ for square matrix multiplication, which led to a improvement from $\omega<2.38719$ to $\omega<2.375477$.

A noteworthy point is that our algorithm directly leads to improved lower bounds on $\alpha$ while, as already mentioned, to obtain a nontrivial lower bound on $\alpha$ using the basic construction $F_{q}$ (as done in ) a specific methodology was needed. Our approach can then be considered as a general framework to study rectangular matrix multiplication, which leads to a unique optimization problem that gives upper bounds on $\omega(1,1,k)$ for any value of $k$.

1 Applications

As mentioned in the beginning of the introduction, improvements on the time complexity of rectangular matrix multiplication give faster algorithms for a multitude of computational problems. In this subsection we describe quantitatively the improvements that our new upper bounds imply for some of these problems: sparse square matrix multiplication, the all-pairs shortest paths problem and computing dynamically the transitive closure of a graph.

Yuster and Zwick have shown how fast algorithms for rectangular matrix multiplication can be used to construct fast algorithms for computing the product of two sparse square matrices (this result has been generalized to the product of sparse rectangular matrices in , and the case where the output matrix is also sparse has been studied in ). More precisely, let $M$ and $M^{\prime}$ be two $n\times n$ matrices such that each matrix has at most $m$ non-zero entries, where $0\leq m\leq n^{2}$. Yuster and Zwick showed that the product of $M$ and $M^{\prime}$ can be computed in time

where $\lambda_{m}$ is the solution of the equation $\lambda_{m}+\omega(1,1,\lambda_{m})=2\log_{n}(m)$. Using the upper bounds on $\omega(1,1,k)$ of Equation (1) with the values $\alpha<0.294$ and $\omega<2.376$, this gives the complexity depicted in Figure 2.

These upper bounds can be of course directly improved by using the new upper bound on $\omega$ by Vassilevska Williams and the new lower bound on $\alpha$ given in the present work, but the improvement is small. A more significant improvement can be obtained by using directly the upper bounds on $\omega(1,1,k)$ presented in Figure 1, which gives the new upper bounds on the complexity of sparse matrix multiplication depicted in Figure 2. For example, for $m=n^{4/3}$, we obtain complexity $O(n^{2.087})$, which is better than the original upper bound $O(n^{2.1293...})$ obtained from Equation (1) with $\alpha>0.294$ and $\omega<2.376$. Note that replacing $\omega<2.376$ with the the best known bound $\omega<2.3727$ only decreases the latter bound to $O(n^{2.1287...})$. Thus, even if the algorithms presented in the present paper do not give any improvement on $\omega$ (i.e., for the product of dense square matrices), we do obtain improvements for computing the product of two sparse square matrices.

Graph algorithms.

Zwick has shown how to use rectangular matrix multiplication to compute, with high probability, the all-pairs shortest paths in weighted direct graphs where the weights are bounded integers. The time complexity obtained is $O(n^{2+\mu+\epsilon})$, for any constant $\epsilon>0$, where $\mu$ is the solution of the equation $\omega(1,1,\mu)=1+2\mu$. Using the upper bounds on $\omega(1,1,k)$ of Equation (1) with $\alpha>0.294$ and $\omega<2.376$, this gives $\mu<0.575$ and thus complexity $O(n^{2.575+\epsilon})$. This reduction to rectangular matrix multiplication is the asymptotically fastest known approach for weighted directed graphs with small integer weights.

Our results (see Table 1) show that $\omega(1,1,0.5302)<2.0604$, which gives the upper bound $\mu<0.5302$. We thus obtain the following result.

There exists a randomized algorithm that computes the shortest paths between all pairs of vertices in a weighted directed graph with bounded integer weights in time $O(n^{2.5302})$, where $n$ is the number of vertices in the graph.

Note that, even if $\omega=2$, the complexity of Zwick’s algorithm is $O(n^{2.5+\epsilon})$. In this perspective, our improvements on the complexity of rectangular matrix multiplication offer a non-negligible speed-up for the all-pairs shortest paths problem in this setting.

The same approach can be used to improve several other existing graph algorithms. Let us describe another example: algorithms for computing dynamically the transitive closure of a graph. Demetrescu and Italiano presented a randomized algorithm for the dynamic transitive closure of directly acyclic graph with $n$ vertices that answers queries in $O(n^{\mu})$ time, and performs updates in $O(n^{1+\mu+\epsilon})$ time, for any $\epsilon>0$. Here $\mu$ is again the solution of the equation $\omega(1,1,\mu)=1+2\mu$. This was the first algorithm for this problem with subquadratic time complexity. This result have been generalized later to general graphs, with the same bounds, by Sankowski . Our new upper bounds thus show the existence of an algorithm for the dynamic transitive closure that answers queries in $O(n^{0.5302})$ time and performs updates in $O(n^{1.5302})$ time.

2 Overview of our techniques and organization of the paper

Before presenting an overview of the techniques used in this paper, we will give an informal description of algebraic complexity theory (the contents of which will be superseded by the formal presentation of these notions in Section 2). In this paper we will use, for any positive integer $n$, the notation $[n]$ to represent the set $\{1,\ldots,n\}$.

The matrix multiplication of an $m\times n$ matrix by an $n\times p$ matrix can be represented by the following trilinear form, denoted as $\langle m,n,p\rangle$:

where $x_{rs}$, $y_{st}$ and $z_{rt}$ are formal variables. This form can be interpreted as follows: the $(r,t)$-th entry of the product of an $m\times n$ matrix $M$ by an $n\times p$ matrix $M^{\prime}$ can be obtained by setting $x_{ij}=M_{ij}$ for all $(i,j)\in[m]\times[n]$ and $y_{ij}=M^{\prime}_{ij}$ for all $(i,j)\in[n]\times[p]$, setting $z_{rt}=1$ and setting all the other $z$-variables to zero. One can then think of the $z$-variables as formal variables used to record the entries of the matrix product.

More generally, a trilinear form $t$ is represented as

An exact (bilinear) algorithm computing $t$ corresponds to an equality of the form

A sum $\sum_{i}t_{i}$ of trilinear forms is a direct sum if the $t_{i}$’s do not share variables. Informally, Schönhage’s asymptotic sum inequality for rectangular matrix multiplication states that, if the form $t$ can be converted (in the $\lambda$-approximation sense) into a direct sum of $c$ trilinear forms, each form being isomorphic to $\langle m,m,m^{k}\rangle$, then

This suggests that good bounds on $\omega(1,1,k)$ can be obtained if the form $t$ can be used to derive many independent (i.e., not sharing any variables) matrix multiplications. This approach has been applied to derive almost all new bounds on matrix multiplication since its discovery in 1981 by Schönhage.

Overview of our techniques.

Our algorithm uses, as its basic construction, the trilinear form $F_{q}\otimes F_{q}$ from , which can be written as a sum of fifteen terms $T_{ijk}$, for all fifteen nonnegative integers $i,j,k$ such that $i+j+k=4$:

If the sum were direct, then, from Schönhage’s asymptotic sum inequality and since an upper bound on the rank of $F_{q}\otimes F_{q}$ is easy to obtain, this would reduce the problem to the analysis of each part $T_{ijk}$. This is unfortunately not the case: the $T_{ijk}$’s share variables. To solve this problem, the basic construction is manipulated in order to obtain a direct sum, similarly to . The first step is to take the $N$-th tensor product of the basis construction, where $N$ is a large integer. This gives:

We will take fifteen integers $a_{ijk}$ and show how the form $(F_{q}\otimes F_{q})^{\otimes N}$ can be transformed, by zeroing variables, into a direct sum of a large number of forms $T_{IJK}$ in which each $T_{IJK}$ is such that

The main difference here is that, in , the symmetry of square multiplication implied that the $a_{ijk}$’s could be taken invariant under permutation of indices, with means that only four parameters ($a_{004}$, $a_{013}$, $a_{022}$ and $a_{112}$) needed to be considered. In our case, we still impose the condition $a_{ijk}=a_{ikj}$, but not more. This reduces the number of parameters to nine: $a_{004}$, $a_{400}$, $a_{013}$, $a_{103}$, $a_{301}$, $a_{022}$, $a_{202}$, $a_{112}$ and $a_{211}$. Many nontrivial technical problems arise from this larger number of parameters. In particular, the equations that occur during the analysis do not have a unique solution and an optimization step is necessary. This is similar to the difficulties that appeared in the analysis of the basis construction $F_{q}^{\otimes 4}$ (for square matrix multiplication) done in . We will show that this further optimization step essentially imposes the additional (nonlinear) constraint $a_{013}a_{202}a_{112}=a_{103}a_{022}a_{211}$.

Showing that $(F_{q}\otimes F_{q})^{\otimes N}$ can be transformed into a direct sum of many isomorphic forms, as claimed, was also used in previous works based on the approach by Coppersmith and Winograd. Our setting is nevertheless more general than in , for the following two reasons. First, our approach is asymmetric since our parameters $a_{ijk}$ are not invariant under permutations of the indices. Second, the technical problems due to the presence of many parameters require more precise arguments. The former complication was addressed implicitly in , and explicitly in . The latter complication was addressed in . Here we need to deal with these two complications simultaneously, which involves a careful analysis. Instead of approaching this task directly in the language of trilinear forms, we give a graph-theoretic interpretation of it, which will make the exposition more intuitive, and also simplify the analysis. Each form $T_{IJK}$ will correspond to one vertex in a graph, and an edge in the graph will represent the fact that two forms share one index. We will interpret the task of converting the sum $(F_{q}\otimes F_{q})^{\otimes N}$ into a direct sum (i.e., a sum where the non-zero forms $T_{IJK}$ do not share any index) as the task of converting the graph, by using only simple graph operations, into an edgeless subgraph. We will present algorithms solving this latter graph-theoretic task and show that a large edgeless subgraph can be obtained, which means that many forms $T_{IJK}$ not sharing any index can be constructed from $(F_{q}\otimes F_{q})^{\otimes N}$.

Now that we have a direct sum of many forms, each form being isomorphic to (2), the only thing to do before applying Schönhage’s asymptotic sum inequality is to show that the form (2) is isomorphic to a direct sum of matrix products $\langle m,m,m^{k}\rangle$. Some of the $T_{ijk}$’s (more precisely, all the $T_{ijk}$’s except $T_{112}$, $T_{121}$ and $T_{211}$) can be analyzed in a straightforward way, since they correspond to matrix products, as originally observed in . The forms $T_{112}$, $T_{121}$ and $T_{211}$ are delicate to analyze since they do not correspond to matrix products. In (see also ), they were analyzed individually through the concept of “value”, a quantity that evaluates the number of square matrix products (and their size) that can be created from the form under consideration. This is nevertheless useless for estimating $\omega(1,1,k)$, except when $k=1$, because the value is intrinsically symmetric (in particular, the values of $T_{112}$, $T_{121}$ and $T_{211}$ are identical), while here we are precisely interested in breaking the symmetry in order to obtain bounds for rectangular matrix multiplication. Instead, we will analyze the term

globally. This is the key new idea leading to our new bounds on $\alpha$ and more generally on $\omega(1,1,k)$ for any $k\neq 1$. Note that this difficulty was not present in previous works on rectangular matrix multiplication : for simpler basic constructions such as $F_{q}$, all the smaller parts correspond to matrix products. We will show that $T_{112}$, $T_{121}$ and $T_{211}$ can be converted into a large number of objects called “$\mathscr{C}$-tensors” in Strassen’s terminology . This will be done by relying on the graph-interpretation we introduced and showing how this conversion can be interpreted as finding large cliques in a graph (this is the main reason why we developed this graph-theoretic interpretation). While the fact that the form $T_{112}$ corresponds to a sum of $\mathscr{C}$-tensors was briefly mentioned in , and a proof sketched, we will need a complete analysis here. We will in particular rely on the fact that the $\mathscr{C}$-tensors obtained from $T_{112}$, $T_{121}$ and $T_{211}$ are not identical. The success of our approach comes from the discovery that these $\mathscr{C}$-tensors are actually “complementary”: while the $\mathscr{C}$-tensors obtained individually from $T_{112}$, $T_{121}$ and $T_{211}$ do not give any improvement for the exponent of rectangular matrix multiplication, their combination (i.e., the $\mathscr{C}$-tensors corresponding to the whole term (3)) does lead to improvements when analyzed globally by the “laser method” developed by Strassen . This will show that the form (3), and thus the form (2) as well, is isomorphic to a direct sum of matrix products $\langle m,m,m^{k}\rangle$.

Finally, Schönhage’s asymptotic sum inequality will give an inequality, depending on the parameters $a_{ijk}$, that involves $\omega(1,1,k)$. Our new upper bounds on $\omega(1,1,k)$ are obtained by optimizing these parameters. While this is done essentially though numerical calculations, the new lower bound on $\alpha$ requires a more careful analysis where the optimal values of all but a few of the parameters are found analytically.

Higher powers.

A natural question is whether our bounds can be improved by taking higher tensor powers of $F_{q}$ as the basic algorithm, i.e., taking $F_{q}^{\otimes r}$for $r>2$. As can be expected from the analysis for $r=2$ we have outlined above, the analysis is much more difficult than in the square case, for two main reasons. The first reason is that the construction is not symmetric and thus more parameters have to be considered. This problem can be nevertheless addressed through a systematic framework similar to the one described in — this is actually quite accessible without using a computer for $r=4$. The second, and more fundamental, reason is that the analysis of the smaller parts is different from the square case since it does not use the concept of value. We solved this problem for $r=2$ by applying Strassen’s laser method globally on the combination of $T_{112}$, $T_{121}$ and $T_{211}$, which is the key technical contribution of this paper. For larger values of $r$ the same approach can in principle be used, but other techniques seem to be necessary to convert these ideas into a systematic framework.

Organization of the paper.

Section 2 describes formally the notions of trilinear forms and Strassen’s laser method. Section 3 presents in details the basic construction $F_{q}\otimes F_{q}$ from and some of its properties. Section 4 describes the graph-theoretic problems that will arise in the analysis of our trilinear forms. Section 5 describes our algorithm, and Section 6 shows how to use this algorithm to derive the optimization problem giving our new upper bounds on $\omega(1,1,k)$. Finally, the optimization is done in Section 7.

Preliminaries

In this section we present known results about trilinear forms, Strassen’s laser method and Salem-Spencer sets that we will use in this paper. We refer to for an extensive treatment of the first two topics.

It will be convenient for us to use an abstract approach and represent trilinear forms as tensors. Our presentation is independent from what was informally defined and stated in Subsection 1.2, but describes essentially the same contents. We thus encourage the reader who encounter these notions for the first time to refer at Subsection 1.2 for concrete illustrations.

The tensor corresponding to the matrix multiplication of an $m\times n$ matrix by an $n\times p$ matrix is the tensor of format $(m\times n,n\times p,m\times p)$ with coefficients

This tensor will be denoted by $\langle m,n,p\rangle$.

This new tensor is called a restriction of $t$. Intuitively, the fact that a tensor $t^{\prime}$ is a restriction of $t$ means that an algorithm computing $t$ can be converted into an algorithm computing $t^{\prime}$ that uses the same amount of multiplications (i.e., an algorithm with essentially the same complexity). We now give the definition of degeneration of tensors.

Intuitively, the fact that a tensor $t^{\prime}$ is a degeneration of a tensor $t$ means that an algorithm computing $t$ can be converted into an “approximate algorithm” computing $t^{\prime}$ with essentially the same complexity. The notion of degeneration can be used to define the notion of border rank.

Let $t\in U\otimes V\otimes W$ and $t^{\prime}\in U^{\prime}\otimes V^{\prime}\otimes W^{\prime}$ be two tensors. We can naturally define the direct sum $t\oplus t^{\prime}$, which is a tensor in $(U\oplus U^{\prime})\otimes(V\oplus V^{\prime})\otimes(W\oplus W^{\prime})$, and the tensor product $t\otimes t^{\prime}$, which is a tensor in $(U\otimes U^{\prime})\otimes(V\otimes V^{\prime})\otimes(W\otimes W^{\prime})$. For any integer $c\geq 1$, we will denote the tensor $t\oplus\cdots\oplus t$ (with $c$ occurrences of $t$) by $c\cdot t$ and the tensor $t\otimes\cdots\otimes t$ (with $c$ occurrences of $t$) by $t^{\otimes c}$. The degeneration of tensors has the following properties.

Let $t_{1},t_{1}^{\prime},t_{2}$ and $t_{2}^{\prime}$ be four tensors. Suppose that $t^{\prime}_{1}\unlhd t_{1}$ and $t^{\prime}_{2}\unlhd t_{2}$. Then $t^{\prime}_{1}\oplus t^{\prime}_{2}\unlhd t_{1}\oplus t_{2}$ and $t^{\prime}_{1}\otimes t^{\prime}_{2}\unlhd t_{1}\otimes t_{2}$.

Schönhage’s asymptotic sum inequality will be one of the main tools used to prove our bounds. Its original statement is for estimating the exponent of square matrix multiplication, but it can be easily generalized to estimate the exponent of rectangular matrix multiplication as well. We will use the following form, which has been also used implicitly in . A proof can be found in .

Let $k$, $m$ and $c$ be three positive integers. Let $t$ be a tensor such that $c\cdot\langle m,m,m^{k}\rangle\unlhd t$. Then

Theorem 2.1 states that, if the form $t$ can be degenerated (i.e., approximately converted, in the sense of Definition 2.1) into a direct sum of $c$ forms, each being isomorphic to $\langle m,m,m^{k}\rangle$, then the inequality $c\cdot m^{w(1,1,k)}\leq\underline{R}(t)$ holds. Note that this is a powerful technique, since the concepts of degeneration and border rank refer to “approximate algorithms”, while $\omega(1,1,k)$ refers to the complexity of exact algorithms for rectangular matrix multiplication.

2 Strassen’s laser method and 𝒞\mathscr{C}-tensors

Strassen introduced in 1986 a new approach, often referred as the laser method, to derive upper bounds on the exponent of matrix multiplication. To the best of our knowledge, all the applications of this method have focused so far on square matrix multiplication, in which case several simplifications can be done due to the symmetry of the problem. In this paper we will nevertheless need the full power of the laser method, and in particular the notion of $\mathscr{C}$-tensor introduced in , to derive our new bounds on the exponent of rectangular matrix multiplication. The exposition below will mainly follow .

Let $t\in U\otimes V\otimes W$ be a tensor. Suppose that $U$, $V$ and $W$ decompose as direct sums of subspaces as follows:

Denote by $D$ this decomposition. We say that $t$ is a $\mathscr{C}$-tensor with respect to $D$ if $t$ can be written as

where each $t_{ijk}$ is a tensor in $U_{i}\otimes V_{j}\otimes W_{k}$. The support of $t$ is defined as

and the nonzero $t_{ijk}$’s are called the components of $t$. We will usually omit the reference to $D$ when there is no ambiguity or when the decomposition does not matter.

for all $(i,j,k)\in\Psi$, $a(i)+b(j)+c(k)=0$;

for all $(i,j,k)\in\Phi\backslash\Psi$, $a(i)+b(j)+c(k)>0$.

Finally, we mention that the concept of $\mathscr{C}$-tensor is preserved by the tensor product. We will just state this property for the restricted class of $\mathscr{C}$-tensors that we will encounter in this paper (for which the precise decompositions do not matter), and refer to or to Section 7 in for a complete treatment.

3 Salem-Spencer sets

Salem and Spenser have shown the existence of very dense sets with no length-3 arithmetic progression.

We refer to these sets as Salem-Spencer sets. They can be constructed in time polynomial in $M$. Note that this construction has been improved by Behrend , but the above statement will be enough for our purpose.

Coppersmith-Winograd’s construction

In this section we describe the construction by Coppersmith and Winograd , which we will use as the basis of our algorithm, and several of its properties.

In this trilinear form the $x$-variables are $x_{0},x_{1},\ldots,x_{q+1}$. Similarly, the number of $y$-variables is $(q+2)$ and the number of $z$-variables is $(q+2)$ as well. Define the form

It is easy to check that the form $F_{q}$ can be written as $F_{q}=F^{\prime}_{q}+\lambda\cdot F^{\prime\prime}_{q}$, where $F^{\prime\prime}_{q}$ is a polynomial in $\lambda$ and in the $x$-variables, $y$-variables and $z$-variables. In the language of Section 2, this means that $F^{\prime}_{q}\unlhd F_{q}$ and, informally, this means that an algorithm computing $F_{q}$ can be converted into an algorithm computing $F^{\prime}_{q}$ with the same complexity. Note that $\underline{R}(F_{q})\leq q+2$ since, by definition, $F_{q}$ is the sum of $q+2$ products.

A more complex construction is proposed in Section 8 of . It is obtained by taking the tensor product of $F_{q}$ by itself. By Proposition 2.1 we know that $F^{\prime}_{q}\otimes F^{\prime}_{q}\unlhd F_{q}\otimes F_{q}$. Consider the tensor product of $F^{\prime}_{q}$ by itself:

Moreover we know that $\underline{R}(F_{q}\otimes F_{q})\leq(q+2)^{2}$, since $F_{q}\otimes F_{q}$ can be written using $(q+2)^{2}$ multiplications.

We will later need to analyze all the forms $T_{ijk}$. It happens, as observed in , that most of these forms (all the forms except $T_{112}$, $T_{121}$ and $T_{211}$) can be analyzed in a straightforward way, since they are isomorphic to the following matrix products:

Graph-Theoretic Problems

In this section we describe and solve several graph-theoretic problems that will arise in the analysis of our trilinear forms. While the presentation given here is independent from the remaining of the paper, the reader may prefer to read Section 5 before going through this section.

Let $\tau$ be a fixed positive integer. Let $N$ be a large integer and define the set

Define the three coordinate functions $f_{1},f_{2},f_{3}\colon[\tau]^{N}\times[\tau]^{N}\times[\tau]^{N}\to[\tau]^{N}$ as follows.

From the definition of $\Lambda$, two distinct elements in $\Lambda$ cannot agree on more than one coordinate. Since this simple observation will be crucial in our analysis, we state it explicitly as follows.

Let $u$ and $v$ be two elements in $\Lambda$. If $f_{i}(u)=f_{i}(v)$ for more than one index $i\in\{1,2,3\}$, then $u=v$.

Let $U$ be a subset of $\Lambda$ such that there exist integers $\mathcal{N}_{1},\mathcal{N}_{2}$ and $\mathcal{N}_{3}$ for which the following property holds: for any $I\in[\tau]^{N}$,

This means that, for any $i\in\{1,2,3\}$ and any $I\in[\tau]^{N}$, the size of the set $f_{i}(I)^{-1}$ is either $0$ or $\mathcal{N}_{i}$. Let us write $|f_{1}(U)|=T_{1}$, $|f_{2}(U)|=T_{2}$ and $|f_{3}(U)|=T_{3}$. It is easy to see that

We are interested in stating asymptotic results holding when $N$ goes to infinity. Through this section the $\mathcal{N}_{i}$’s and the $T_{i}$’s will be strictly increasing functions of $N$.

Let $G$ be the (simple and undirected) graph with vertex set $U$ in which two distinct vertices $u$ and $v$ are connected if and only there exists one index $i\in\{1,2,3\}$ such that $f_{i}(u)=f_{i}(v)$. The goal will be to modify the graph $G$ to obtain a subgraph satisfying some specific properties. The only modification we allow is to remove all the vertices with a given sequence at a given position: given a sequence $I\in[\tau]^{N}$ and a position $s\in\{1,2,3\}$, remove all the vertices $u$ (if any) such that $f_{i}(u)=I$. We call such an operation a removal operation. The reason why only such removal operations are allowed is that they will correspond, when considering trilinear forms, to setting to zero some variables, which is one of the only operations that can be performed on trilinear forms.

While not stated explicitly in graph-theoretic terms, the key technical result by Coppersmith and Winograd is a method to convert, when $\mathcal{N}_{1}=\mathcal{N}_{2}=\mathcal{N}_{3}$, the graph $G$ into an edgeless graph that still contains a non-negligible fraction of the vertices. We state this result in the following theorem.

Suppose that $\mathcal{N}_{1}=\mathcal{N}_{2}=\mathcal{N}_{3}$. Then, for any constant $\epsilon>0$, the graph $G$ can be converted, with only removal operations, into an edgeless graph with $\Omega\left(\frac{T_{1}}{\mathcal{N}_{1}^{\epsilon}}\right)$ vertices.

In this section we will give several generalizations of this result. In Subsection 4.2 we state our generalizations. Then, in Subsections 4.3–4.6, we describe the algorithms and prove the results. We stress that, in this section as in , the number of removal operations (i.e., the time complexity of the algorithms) is irrelevant. This is because, in the applications of these results to matrix multiplication, the parameter $N$ will be treated as a large constant independent of the size of the matrices considered.

2 Statement of our results

The generalization we consider assume the existence of a known set $U^{\ast}\subseteq U$ such that

$|f_{i}(U^{\ast})|=T_{i}$ for each $i\in\{1,2,3\}$;

there exist integers $\mathcal{N}^{\ast}_{1},\mathcal{N}^{\ast}_{2}$ and $\mathcal{N}^{\ast}_{3}$ such that

for each $I\in[\tau]^{N}$ and each $i\in\{1,2,3\}$.

Note that we have necessarily $T_{1}\mathcal{N}^{\ast}_{1}=T_{1}\mathcal{N}^{\ast}_{2}=T_{1}\mathcal{N}^{\ast}_{2}$.

The first problem considered is again to convert the graph $G$ into an edgeless subgraph that contains a non-negligible fraction of the vertices using only removal operations, but we additionally require that all the remaining vertices are in $U^{\ast}$. Our first result is the following theorem.

For any constant $\epsilon>0$, the graph $G$ can be converted, with only removal operations, into an edgeless graph with

vertices, all of them being in $U^{\ast}$.

Theorem 4.1 is a special case of Theorem 4.2, for $U^{\ast}=U$. The case $\mathcal{N}_{1}=\mathcal{N}_{2}=\mathcal{N}_{3}$ has been proved implicitly by Stothers and Vassilevska Williams .

Our second problem deals with another kind of conversion. Remember that, from the definition of the graph $G$ and Fact 1, for any edge connecting two vertices $u$ and $v$ in $G$ there exists exactly one index $i\in\{1,2,3\}$ such that $f_{i}(u)=f_{i}(v)$. Let us define the concept of 1-clique as follows.

A 1-clique in the graph $G$ is a set $U^{\prime}\subseteq U$ for which there exists a sequence $I\in[\tau^{N}]$ such that $f_{1}(u)=I$ for all $u\in U^{\prime}$. The size of the 1-clique is $|U^{\prime}|$.

Our second result shows how to convert, using only removal operations, the graph $G$ into a graph with vertices in $U^{\ast}$ that is the disjoint union of many large 1-cliques. The formal statement follows.

Suppose that $\mathcal{N}_{1}\geq\mathcal{N}_{2}\geq\mathcal{N}_{3}$. Assume that $\frac{\mathcal{N}_{2}T_{1}}{\mathcal{N}_{1}^{\ast}}+\frac{\mathcal{N}_{2}}{T_{1}}<\frac{1}{1024}$. Then, for any constant $\epsilon>0$, the graph $G$ can be converted, with only removal operations, into a graph satisfying the following conditions:

all the vertices of the graph are in $U^{\ast}$;

each connected component is a 1-clique (i.e., the graph is a disjoint union of 1-cliques);

among these 1-cliques, there are $\Omega\left(\frac{T_{1}}{\mathcal{N}_{2}^{\epsilon}}\right)$ 1-cliques that have size $\Omega\left(\frac{\mathcal{N}_{1}^{\ast}}{\mathcal{N}_{2}}\right)$.

Note that, when only removal operations are allowed, the graph obtained is necessary a subgraph of $G$ induced be a subset of its vertices. Theorem 4.3 thus states that there exist 1-cliques $U_{r}\subseteq U^{\ast}$ such that the graph obtained after the removal operations is the subgraph of $G$ induced by $\cup_{r}U_{r}$, at least $\Omega\left(T_{1}/\mathcal{N}_{2}^{\epsilon}\right)$ of these $U_{r}$’s have size $\Omega\left(\mathcal{N}_{1}^{\ast}/\mathcal{N}_{2}\right)$, and for any $r\neq r^{\prime}$ there is no edge with one extremity in $U_{r}$ and the other extremity in $U_{r^{\prime}}$. We mention that the constant $1/1024$ in the assumption of Theorem 4.3 is chosen only for concreteness. The same theorem actually holds even for weaker conditions on $\mathcal{N}^{\ast}_{1},T_{1}$ and $\mathcal{N}_{2}$, but this simpler version will be sufficient for our purpose.

3 Choice of the weight functions

Let us introduce the notion of a compatible vertex.

A vertex $u\in{U}$ is compatible if $b_{i}(f_{i}(u))\in\Gamma$ for each $i\in\{1,2,3\}$. Let $V$ be the set of vertices in $U$ that are compatible, and denote $V^{\ast}=V\cap U^{\ast}$.

We stress that the definition of compatibility (and thus the definitions of $V$ and $V^{\ast}$ too) depend of the choice of $\Gamma$ and of the weights $\omega_{i}$. Using the fact that $\Gamma$ is a Salem-Spencer set we can give the following simple but very useful characterization of compatible vertices.

Let $i\in\{1,2,3\}$ and $i^{\prime}\in\{1,2,3\}$ be any two distinct indexes. Then a vertex $u\in U$ is compatible if and only if $b_{i}(f_{i}(u))=b_{i^{\prime}}(f_{i^{\prime}}(u))=b$ for some $b\in\Gamma$.

Let us take a vertex $u\in U$, and write $f_{1}(u)=I$, $f_{2}(u)=J$ and $f_{3}(u)=K$.

Suppose that $b_{i}(f_{i}(u))=b_{i^{\prime}}(f_{i^{\prime}}(u))=b$ for some $b\in\Gamma$, where $i$ and $i^{\prime}$ are distinct. For instance, suppose that $i=1$ and $i^{\prime}=2$. Then, since $M$ is a prime, the above property implies that $b_{3}(K)=b$, which means that $u$ is compatible. The same conclusion is true for the other choices of $i$ and $i^{\prime}$.

Now suppose that $u$ is compatible. From the definition of a Spencer-Salem set, we can conclude that there exists an element $b\in\Gamma$ such that $b_{1}(I)=b_{2}(J)=b_{3}(K)=b$. ∎

4 The first pruning

Similarly to , the first pruning simply eliminates all the nodes $u\in U$ that are not compatible. Note that this can be done using removal operations: for each $i\in\{1,2,3\}$, we remove all the vertices $w$ such that $f_{i}(w)\notin b_{i}^{-1}(\Gamma)$. The vertices remaining are precisely those in $V$. Among those remaining vertices, the vertices in $U^{\ast}$ are precisely those in $V^{\ast}=V\cap U^{\ast}$.

We now evaluate the expectation of $|V^{\ast}|$. The proof is very similar to what was shown in for the case $U=U^{\ast}$, and to what was shown in for $\mathcal{N}^{\ast}_{1}=\mathcal{N}^{\ast}_{2}=\mathcal{N}^{\ast}_{3}$.

Let $E$ be the edge set of the subgraph of $G$ induced by $V$: it consists of all edges connecting two distinct vertices $u$ and $v$ in $V$ such that $f_{i}(u)=f_{i}(v)$ for some $i\in\{1,2,3\}$. Let $E^{\prime}\subseteq E$ be the subset of edges in $E$ with (at least) one extremity in $V^{\ast}$. Let $E^{\prime\prime}\subseteq E^{\prime}$ be the subset of edges in $E^{\prime}$ connecting two vertices $u$ and $v$ such that $f_{1}(u)\neq f_{1}(v)$ (which means that either $f_{2}(u)=f_{2}(v)$ or $f_{3}(u)=f_{3}(v)$). The following lemma gives upper bounds on the expectations of $|E^{\prime}|$ and $|E^{\prime\prime}|$. The proof can be considered as a generalization of similar statements in .

We show that, for any index $i\in\{1,2,3\}$, the expected number of ordered pairs $(u,v)$ with $u\in V^{\ast}$ and $v\in V\backslash\{u\}$ such that $f_{i}(u)=f_{i}(v)$ is exactly

The expectation of the number of edges (i.e., unordered pairs) is necessarily smaller.

The factor $T_{1}\mathcal{N}_{1}^{\ast}$ counts the number of vertices in $U^{\ast}$. For any vertex $u\in U^{\ast}$, there are exactly $\mathcal{N}_{i}-1$ vertices $v\in U\backslash\{u\}$ such that $f_{i}(v)=f_{i}(u)$.

Let $u$ be a vertex in $U^{\ast}$ and $v$ be a vertex in $U\backslash\{u\}$ such that $f_{i}(v)=f_{i}(u)$. Take another index $i^{\prime}\in\{1,2,3\}\backslash\{i\}$ arbitrarily. From Lemma 4.1, both $u$ and $v$ are in $V$ if and only if

for some element $b\in\Gamma$. This happens with probability $|\Gamma|/M^{3}$ since the random variables $b_{i}(f_{i}(u))$, $b_{i^{\prime}}(f_{i^{\prime}}(u))$, and $b_{i^{\prime}}(f_{i^{\prime}}(v))$ are mutually independent. From the linearity of the expectation, the expected number of ordered pairs is $T_{1}\mathcal{N}_{1}^{\ast}(\mathcal{N}_{i}-1)$ times this probability. ∎

Lemmas 4.2 and 4.3 focused on expected values and were proven, essentially, by the linearity of the expectation. This was sufficient for the applications to square matrix multiplication presented in , and this will be sufficient for proving Theorem 4.2 as well. Since, in order to prove Theorem 4.3, we will need a more precise analysis of the behavior of the random variables considered, we now prove the following lemma, which gives a lower bound on the probability that the subgraph induced by $V^{\ast}$ has many large $1$-cliques.

With probability (on the choice of the weights $\omega_{i}$) at least $1-\frac{4MT_{1}}{\mathcal{N}_{1}^{\ast}}-\frac{4M}{T_{1}|\Gamma|}$, there exists a set $R\subseteq[\tau]^{N}$ satisfying the following two conditions:

for any $I\in R$, there exist at least $\frac{\mathcal{N}_{1}^{\ast}}{2M}$ vertices $u\in V^{\ast}$ such that $f_{1}(u)=I$.

Let us consider the set $f_{1}(U^{\ast})=\{f_{1}(u)\>|\>u\in U^{\ast}\}$. For each element $I\in f_{1}(U^{\ast})$, define the set

Note that $|f_{1}(U^{\ast})|=T_{1}$, and $|S_{I}|=\mathcal{N}_{1}^{\ast}$ for each $I\in f_{1}(U^{\ast})$.

Fix an element $I\in f_{1}(U^{\ast})$ and define

This random variable represents the number of vertices from $S_{I}$ that are mapped by $b_{2}\circ f_{2}$ into $b_{1}(I)$. For any vertex $u=(I,J,K)\in S_{I}$, we have the equivalence

where the second inequality is obtained by Chebyshev’s inequality.

From the union bound we can conclude that, with probability at least $1-\frac{4MT_{1}}{\mathcal{N}_{1}^{\ast}}-\frac{4M}{T_{1}|\Gamma|}$, the inequality $\left|R\right|\geq T_{1}|\Gamma|/(2M)$ holds and simultaneously, for each element $I\in R$, there exist at least $\mathcal{N}_{1}^{\ast}/(2M)$ vertices $u\in U^{\ast}$ such that $f_{1}(u)=I$ and $b_{2}(f_{2}(u))=b_{1}(I)$. These vertices are in $V^{\ast}$ by Lemma 4.1. ∎

5 The second pruning: first version and proof of Theorem 4.2

In this subsection $M$ is an arbitrary prime number such that $2(\mathcal{N}_{1}+\mathcal{N}_{2}+\mathcal{N}_{3})<M<4(\mathcal{N}_{1}+\mathcal{N}_{2}+\mathcal{N}_{3})$.

The first pruning has transformed the graph $G$ into the subgraph induced by $V$. The second pruning, similarly to , will further modify this subgraph by removing vertices in order to obtain a subgraph consisting of isolated vertices from $V^{\ast}$ (i.e., an edgeless graph). This is done by constructing greedily a set $L\subseteq V^{\ast}$ of isolated vertices. Initially $L=\emptyset$ and, at each iteration, either one remaining vertex in $V^{\ast}\backslash L$ will be added to $L$ or several vertices in $V$ will be removed. This will be repeated until there is no remaining vertex in $V^{\ast}\backslash L$. Finally, all the remaining vertices not in $L$ will be removed. The detailed procedure is described in Figure 3, where $\overline{V}$ represents the set of remaining vertices (initially $\overline{V}=V$). Note that the procedure slightly differs from what was done in since we need to take in consideration the asymmetry of the problem.

Let $\overline{V_{f}}$ denote the contents of $\overline{V}$ at the end of the procedure. The following proposition, shown using the same ideas as in , shows that what we obtain is a large set of isolated vertices from $V^{\ast}$.

The subgraph of $G$ induced by $\overline{V_{f}}$ is an edgeless graph. Moreover, $\overline{V_{f}}\subseteq V^{\ast}$ and the expectation of $|\overline{V_{f}}|$ (over the choices of $\omega_{j}$) is

Let $L_{f}$ denote the contents of $L$ at the end of the procedure. First observe that $\overline{V_{f}}\subseteq L_{f}$, due to Step 3. Note that any vertex added to $L$ cannot be later removed from $\overline{V}$, since it has no neighbor. Thus $L_{f}\subseteq\overline{V_{f}}$, and we conclude that $\overline{V_{f}}=L_{f}$. This shows in particular that $\overline{V_{f}}\subseteq V^{\ast}$. Moreover, since each vertex in $L$ has no neighbor, the subgraph induced by $\overline{V_{f}}$ is edgeless.

To prove the second part, we will show an upper bound on the number of vertices in $V^{\ast}$ removed from $\overline{V}$ during the loop of Step 2. The bound will be obtained by considering the number of edges from $E^{\prime}$ remaining in the subgraph induced by $\overline{V}$.

Let us consider what happens during Step 2.2. Let $u\in(\overline{V}\cap V^{\ast})\backslash L$ be the vertex currently examined. Suppose that another vertex in $\overline{V}$ sharing one index with $u$ is found. For example, suppose that we find another vertex $v\in\overline{V}$ with $f_{1}(v)=f_{1}(u)$. Let $S=\{w\in\overline{V}\cap V^{\ast}\>|\>f_{2}(w)=f_{2}(u)\}$ be the set of vertices in $V^{\ast}$ eliminated by the consequent removal operation. Observe that this removal operation will eliminate at least ${|S|\choose 2}+1$ new edges from $E^{\prime}$: the edges between two vertices in $S$, and the edge connecting $u$ and $v$. Since ${|S|\choose 2}+1\geq|S|$, the number of vertices in $V^{\ast}$ removed during one execution of Step 2.2 is at most the number of edges eliminated from $E^{\prime}$.

The total number of vertices from $V^{\ast}$ that are removed by the procedure during the loop of Step 2 is thus at most $|E^{\prime}|$, which means that $|\overline{V_{f}}\cap V^{\ast}|\geq|V^{\ast}|-|E^{\prime}|$. Since $\overline{V}\subseteq V^{\ast}$, Lemmas 4.2 and 4.3 imply that the expected number of vertices in $\overline{V_{f}}$ is at least

6 The second pruning: second version and proof of Theorem 4.3

In this subsection $M$ is an arbitrary prime such that $64\mathcal{N}_{2}<M<128\mathcal{N}_{2}$.

The first version of the pruning described in Subsection 4.5 was designed to obtain an edgeless subgraph of $G$. In this subsection we describe how to modify it to obtain a union of many large 1-cliques instead. The detailed procedure of the new pruning algorithm is described in Figure 4. The only difference is that, at Step 2.2, a vertex is not added in $L$ only if it is connected to another vertex with the same second or third index.

Let $\overline{V_{f}}$ denote the contents of $\overline{V}$ at the end of the procedure. By slightly modifying the arguments of the previous subsection, it is easy to see that the resulting graph has only vertices from $V^{\ast}$ and is a disjoint union of 1-cliques (i.e., each connected component is a 1-clique).

The subgraph of $G$ induced by $\overline{V_{f}}$ is a disjoint union of 1-cliques. Moreover, $\overline{V_{f}}\subseteq V^{\ast}$ and $|\overline{V_{f}}|\geq|V^{\ast}|-|E^{\prime\prime}|$.

Let $L_{f}$ denote the contents of $L$ at the end of the procedure. Due to Step 3, we know that $\overline{V_{f}}\subseteq L_{f}$. Moreover, any vertex added to $L$ cannot be later removed from $\overline{V}$, since it has no neighbor with the same second or third index. Thus $L_{f}\subseteq\overline{V_{f}}$, and we conclude that $\overline{V_{f}}=L_{f}$, which shows in particular that $\overline{V_{f}}\subseteq V^{\ast}$. Furthermore, since each vertex in $L$ has no neighbor with the same second or third index, the subgraph induced by $\overline{V_{f}}$ is a disjoint union of 1-cliques.

The inequality $|\overline{V_{f}}|\geq|V^{\ast}|-|E^{\prime\prime}|$ is obtained as in the proof of Proposition 4.1, but replacing the edge set $E^{\prime}$ by $E^{\prime\prime}$. ∎

We now give the proof of Theorem 4.3, by using Lemmas 4.3 and 4.4 to evaluate the size and the numbers of 1-cliques in the resulting graph.

Using Lemma 4.3 with the value $M>64\mathcal{N}_{2}$ and Markov’s bound, we conclude that

Note that the conditions $M<128\mathcal{N}_{2}$ and $\frac{\mathcal{N}_{2}T_{1}}{\mathcal{N}_{1}^{\ast}}+\frac{\mathcal{N}_{2}}{T_{1}}<\frac{1}{1024}$ imply that

Thus the probability that a set $R$ as in Lemma 4.4 exists and the inequality $|E^{\prime\prime}|\leq\frac{T_{1}\mathcal{N}_{1}^{\ast}|\Gamma|}{16M^{2}}$ simultaneously holds is positive. There then exists a choice of the weights $\omega_{0},\omega_{1},\ldots,\omega_{N+1}$ such that this happens. Let us take such a choice.

From Proposition 4.2 we know that at most $|E^{\prime\prime}|$ vertices in $V^{\ast}$ are removed by the second pruning. Then there exists a set $R^{\prime}\subseteq R$ of size $|R^{\prime}|\geq T_{1}|\Gamma|/(4M)$ such that, for any $r^{\prime}\in R^{\prime}$, there are at least $\mathcal{N}_{1}^{\ast}/(4M)$ vertices $u$ with $f_{1}(u)=r^{\prime}$ remaining after the second pruning. This is because, otherwise, from the properties of the set $R$ stated in Lemma 4.4 it would be necessary to remove more than $T_{1}\mathcal{N}_{1}^{\ast}|\Gamma|/(16M^{2})$ vertices during the second pruning. ∎