Combinatorial problems related to matrix multiplication (guest post by Chris Umans)

by

Determining the exponent of matrix multiplication, \omega, is one of the most prominent open problems in algebraic complexity. Strassen famously showed that \omega < 2.81 in 1969, and after a sequence of works culminating in work of Stothers and Williams the best current upper bound is \omega < 2.3727. It is believed that indeed \omega = 2, meaning that there is a family of algorithms with running time O(n^{2 + \epsilon}) for every \epsilon > 0. In this sense, if \omega =2, matrix multiplication exhibits “speedup”: there is no single best asymptotic algorithm, only a sequence of algorithms having running times O(n^a), with a approaching 2. In fact Coppersmith and Winograd showed in 1982 that this phenomenon occurs whatever the true value of \omega is (two, or larger than two), a result that is often summarized by saying “the exponent of matrix multiplication is an infimum, not a minimum.”

Despite the algebraic nature of the matrix multiplication problem, many of the suggested routes to proving \omega = 2 are combinatorial. This post is about connections between one such combinatorial conjecture (the “Strong Uniquely Solvable Puzzle” conjecture of Cohn, Kleinberg, Szegedy and Umans) and some more well-known combinatorial conjectures. These results appear in this recent paper with Noga Alon and Amir Shpilka.

The cap set conjecture, a strengthening, and a weakening

We start with a well-known, and stubborn, combinatorial problem, the “cap-set problem.” A cap-set in Z_3^n is a subset of vectors in Z_3^n with the property that no three vectors (not all the same) sum to 0. The best lower bound is 2.21...^n due to Edel. Let us denote by the “cap set conjecture” the assertion that one can actually find sets of size (3 - o(1))^n. It appears that there is no strong consensus on whether this conjecture is true or false, but one thing that we do know is that it is a popular blog topic (see herehere, here, and the end of this post).

Now it happens that the only triples of elements of Z_3 that sum to 0 are \{0,0,0\}, \{1,1,1\}, \{2,2,2\} and \{1,2,3\} — triples that are “all the same, or all different.” So the cap set conjecture can be rephrased as the conjecture that there are large subsets of vectors in Z_3^n so that for any x, y,z in the set (not all equal), there is some coordinate i such that (x_i, y_i, z_i) are “not all the same, and not all different.” Generalizing from this interpretation, we arrive at a family of much stronger assertions, one for each D: let’s denote by the “Z_D^n conjecture” the assertion that there are subsets of vectors in Z_D^n, of size (D - o(1))^n with the property that for any x, y,z in the set (not all equal), there is some coordinate i such that (x_i, y_i, z_i) are “not all the same, and not all different.” Such sets of size (D - o(1))^n in Z_D^n imply size (3 - o(1))^n-size sets of this type in Z_3^n by viewing each symbol in Z_D as a block of \log_3 D symbols in Z_3, so the Z_D^n conjecture is stronger (i.e. it implies the cap-set conjecture). Indeed, if you play around with constructions you can see that as D gets larger it seems harder and harder to have large sets avoiding triples of vectors for which every coordinate i has (x_i, y_i, z_i) “all different.” Thus one would probably guess that the Z_D^n conjecture is false.

One of the results in our paper is that the Z_D^n conjecture is in fact *equivalent* to falsifying the following well-known sunflower conjecture of Erdos-Szemeredi: there exists an \epsilon > 0 such that any family of at least 2^{(1 - \epsilon)n} subsets of [n] contains a 3-sunflower (i.e., three sets whose pairwise intersections are all equal).

So the intuition that the Z_D^n conjecture is false agrees with Erdos and Szemeredi’s intuition, which is a good sign.

Now let’s return to the cap-set conjecture in Z_3^n. Being a cap set is a condition on *all* triples of vectors in the set. If one restricts to a condition on only some of the triples of vectors, then a construction becomes potentially easier. We will be interested in a “multicolored” version in which vectors in the set are assigned one of three colors (say red, blue, green), and we only require that no triple of vectors x,y,z sums to 0 with x being red, y being blue, and z being green. But a moment’s thought reveals that the problem has become too easy: one can take (say) the red vectors to be all vectors beginning with 01, the green vectors to be all vectors beginning with 00, and the the blue vectors to be all vectors beginning with 1. A solution that seems to recover the original flavor of the problem, is to insist that the vectors come from a collection of red, green, blue triples (x, y,z) with x+y+z = 0; we then require that every red, green, blue triple *except those in the original collection* not sum to 0. So, let’s denote by the “multicolored cap-set conjecture” the assertion that there are subsets of *triples of vectors* from Z_3^n of size (3 - o(1))^n, with each triple summing to 0, and with the property that for any three triples (x_1, y_1,z_1), (x_2, y_2, z_2), (x_3, y_3, z_3) in the set (not all equal), x_1+y_2+z_3 \neq 0.

If S is a cap set in Z_3^n, then the collection of triples \{(x,x,x): x \in S\} constitutes a multicolored cap-set of the same size, so the multicolored version of the conjecture is indeed weaker (i.e. it is implied by the cap-set conjecture).

A matrix multiplication conjecture between the two

The SUSP conjecture of Cohn, Kleinberg, Szegedy, and Umans is the following: there exist subsets of *triples of vectors* from \{0,1\}^n of size (27/4 - o(1))^{n/3}, with each triple summing (in the integers) to the all-ones vector, and with the property that for any three triples [(x_1, y_1,z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)] in the set (not all equal), there is a coordinate i such that x_1[i]+y_2[i]+z_3[i] = 2.

The mysterious constant (27/4)^{1/3} comes from the fact {n \choose {n/3}} \approx (27/4)^{n/3}, and it is easy to see that one cannot have multiple triples with the same “x vector” (or y, or z…). More specifically, “most” triples (x, y, z) that sum to the all-ones vector are balanced (meaning that x, y, z each have weight n/3), and there can be at most {n \choose {n/3}} balanced triples, without repeating an x vector. So the conjecture is that there are actually subsets satisfying the requirements, whose sizes approach this easy upper bound.

If in the statement of the SUSP conjecture, one replaces “there is a coordinate i such that x_1[i]+y_2[i]+z_3[i] = 2” with “there is a coordinate i such that x_1[i]+y_2[i]+z_3[i] \neq 1” one gets the weaker “Uniquely Solvable Puzzle” conjecture instead of the “Strong Uniquely Solvable Puzzle” conjecture. Here one is supposed to interpret the (x,y,z) triples as triples of “puzzle pieces” that fit together (i.e. their 1’s exactly cover the n coordinates without overlap); the main requirement then ensures that no other way of “assembling the puzzle” fits together in this way, thus it is “uniquely solvable.” It is a consequence of the famous Coppersmith-Winograd paper that the Uniquely Solvable Puzzle conjecture is indeed true. Cohn, Kleinberg, Szegedy and Umans showed that if the stronger SUSP conjecture is true, then \omega = 2.

Two of the main results in our paper are that (1) the Z_D^n conjecture implies the SUSP conjecture, and (2) the SUSP conjecture implies the multicolored cap-set conjecture.

So by (1), *disproving the SUSP* conjecture is as hard as proving the Erdos-Szemeredi conjecture (which recall is equivalent to disproving the Z_D^n conjecture). Of course we hope the SUSP conjecture is true, but if it is not, it appears that will be difficult to prove.

And by (2), proving the SUSP conjecture entails proving the multicolored cap-set conjecture. So apart from being a meaningful weakening of the famous cap-set conjecture in Z_3^n, the multicolored cap-set conjecture can be seen as a “warm-up” to (hopefully) proving the SUSP conjecture and establishing \omega = 2. As a start, we show in our paper a lower bound of 2.51^n for multicolored cap-sets, which beats the 2.21^n lower bound of Edel for ordinary cap sets.

Returning to “speedup,” the topic of this blog, notice that the SUSP conjecture, as well as the cap-set, the multicolored cap-set, and the Z_D^n conjectures, all assert that there exist sets of size (c-o(1))^n with certain properties, for various constants c. In all cases c^n is easily ruled out, and so all one can hope for is a sequence of sets, one for each n, whose sizes approach c^n as n grows. If the SUSP conjecture is true, then it is this sequence of sets that directly corresponds to a sequence of matrix multiplication algorithms with running times O(n^a) for a approaching 2. This would then be a concrete manifestation of the “speedup” phenomenon for matrix multiplication.

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: